Document Type
Article
Publication Date
7-12-2025
Publisher
Springer Nature
Abstract
The chromatic polynomial πG(k) of a graph G can be viewed as counting the number of vertices in a family of coloring graphs 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 π(H)G(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 π(P2)G(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.
Recommended Citation
Asgarli, S., Krehbiel, S., Levinson, H. W., & Russell, H. M. (2025). Counting Subgraphs of Coloring Graphs. Graphs and Combinatorics, 41(4), 82. https://doi.org/10.1007/s00373-025-02938-1
Comments
Open access to this article is funded by Santa Clara University Library.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.