Counting Subgraphs of Coloring Graphs

Abstract The chromatic polynomial $$\pi _{G}(k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>π</mml:mi> <mml:mi>G</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> of a graph G can be viewed as counting the number of vertices in a family of coloring graphs $$\mathcal {C}_k(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>π</mml:mi> <mml:mi>G</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msubsup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>π</mml:mi> <mml:mrow> <mml:mi>G</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:msubsup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , 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.