2024/01/23 by Asgarli, Shamil, Krehbiel, Sara, Levinson, Howard W. +1
#05C15 #05C31 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.12883
The chromatic polynomial πG(k) of a graph G can be viewed as counting the number of vertices in a family of coloring graphs \mathcal Ck(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 π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 πG(P2)(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.