Counting Subgraphs of Coloring Graphs

Source abstract

Abstract The chromatic polynomial $$\pi _{G}(k)$$ π G ( k ) of a graph G can be viewed as counting the number of vertices in a family of coloring graphs $$\mathcal {C}_k(G)$$ C k ( G ) associated with (proper) k -colorings of G as a function of the number of colors k . These coloring graphs can be understood as a reconfiguration system. We generalize the chromatic polynomial to $$\pi _G^{(H)}(k)$$ π G ( H ) ( k ) , counting occurrences of arbitrary induced subgraphs H in these coloring graphs, and we prove that these functions are polynomial in k . In particular, we study the chromatic pairs polynomial $$\pi _{G}^{(P_2)}(k)$$ π G ( P 2 ) ( k ) , which counts the number of edges in coloring graphs, corresponding to the number of pairs of colorings that differ on a single vertex. We show two trees share a chromatic pairs polynomial if and only if they have the same degree sequence, and we conjecture that the chromatic pairs polynomial refines the chromatic polynomial in general. We also instantiate our polynomials with other choices of H to generate new graph invariants.