Computing the Chromatic Polynomials of the Six Signed Petersen Graphs

Graphs are a collection of vertices and edges that connect some vertices to others. Signed graphs are graphs whose edges are assigned positive or negative labels and may contain loops. Signed graphs have been useful in understanding phenomena that occur in our society such as, interactions within a group of individuals or the representation of biological networks which allow for further analysis of the relationships that exist in nature. Our work addresses open questions regarding proper colorings of signed graphs, in which the vertices are assigned colors based on rules according to the edge connections and edge labels. We explore the number of proper colorings of these graphs by computing their corresponding chromatic polynomials. In particular, we investigate the six distinct signed Petersen graphs studied by Thomas Zaslavsky (Discrete Math. 312 (2012), no. 9, 1558-1583). For our research, we employ the methods of interpolation, inside-out polytopes and the deletion-contraction algorithm to compute the chromatic polynomials of the six signed Petersen graphs.