{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T14:14:22Z","timestamp":1772028862706,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T00:00:00Z","timestamp":1752278400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T00:00:00Z","timestamp":1752278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009482","name":"Santa Clara University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009482","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The chromatic polynomial <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\pi _{G}(k)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03c0<\/mml:mi>\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of a graph <jats:italic>G<\/jats:italic> can be viewed as counting the number of vertices in a family of coloring graphs <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {C}_k(G)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> associated with (proper) <jats:italic>k<\/jats:italic>-colorings of <jats:italic>G<\/jats:italic> as a function of the number of colors <jats:italic>k<\/jats:italic>. These coloring graphs can be understood as a reconfiguration system. We generalize the chromatic polynomial to <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\pi _G^{(H)}(k)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msubsup>\n                      <mml:mi>\u03c0<\/mml:mi>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>H<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msubsup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, counting occurrences of arbitrary induced subgraphs <jats:italic>H<\/jats:italic> in these coloring graphs, and we prove that these functions are polynomial in <jats:italic>k<\/jats:italic>. In particular, we study the <jats:italic>chromatic pairs polynomial<\/jats:italic>\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\pi _{G}^{(P_2)}(k)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msubsup>\n                      <mml:mi>\u03c0<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>P<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msub>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msubsup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, 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 <jats:italic>H<\/jats:italic> to generate new graph invariants.<\/jats:p>","DOI":"10.1007\/s00373-025-02938-1","type":"journal-article","created":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T13:01:18Z","timestamp":1752325278000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Counting Subgraphs of Coloring Graphs"],"prefix":"10.1007","volume":"41","author":[{"given":"Shamil","family":"Asgarli","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3662-4005","authenticated-orcid":false,"given":"Sara","family":"Krehbiel","sequence":"additional","affiliation":[]},{"given":"Howard W.","family":"Levinson","sequence":"additional","affiliation":[]},{"given":"Heather M.","family":"Russell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,12]]},"reference":[{"key":"2938_CR1","doi-asserted-by":"publisher","unstructured":"Adaricheva, K., Bozeman, C., Clarke, N.E., Haas, R., Messinger, M.E., Seyffarth, K., Smith, H.C.: Reconfiguration graphs for dominating sets, Research trends in graph theory and applications, Assoc. Women Math. Ser., 25, Springer, Cham, 119\u2013135, (2021) https:\/\/doi.org\/10.1007\/978-3-030-77983-2_6,","DOI":"10.1007\/978-3-030-77983-2_6"},{"issue":"2","key":"2938_CR2","doi-asserted-by":"publisher","first-page":"311","DOI":"10.2140\/involve.2018.11.311","volume":"11","author":"F Alvarado","year":"2018","unstructured":"Alvarado, F., Butts, A., Farquhar, L., Russell, H.M.: Forbidden subgraphs of coloring graphs. Involve 11(2), 311\u2013324 (2018). https:\/\/doi.org\/10.2140\/involve.2018.11.311. (1944\u20134176, 1944\u20134184)","journal-title":"Involve"},{"issue":"10","key":"2938_CR3","doi-asserted-by":"publisher","first-page":"2938","DOI":"10.1016\/j.disc.2018.07.007","volume":"341","author":"J Asplund","year":"2018","unstructured":"Asplund, J., Edoh, K., Haas, R., Hristova, Y., Novick, B., Werner, B.: Reconfiguration graphs of shortest paths. Discrete Math. 341(10), 2938\u20132948 (2018). https:\/\/doi.org\/10.1016\/j.disc.2018.07.007. (0012\u2013365X, 1872\u2013681X)","journal-title":"Discrete Math."},{"issue":"7\u20138","key":"2938_CR4","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1177\/0278364904045468","volume":"23","author":"A Abrams","year":"2004","unstructured":"Abrams, A., Ghrist, R.: State complexes for metamorphic robots. Int. J. Robot. Res. 23(7\u20138), 811\u2013826 (2004)","journal-title":"Int. J. Robot. Res."},{"issue":"1","key":"2938_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00373-018-1985-6","volume":"35","author":"P Bhakta","year":"2019","unstructured":"Bhakta, P., Buckner, B.B., Farquhar, L., Kamat, V., Krehbiel, S., Russell, H.M.: Cut-colorings in coloring graphs. Graphs Combin. 35(1), 239\u2013248 (2019). https:\/\/doi.org\/10.1007\/s00373-018-1985-6. (0911\u20130119,1435\u20135914)","journal-title":"Graphs Combin."},{"issue":"8","key":"2938_CR6","doi-asserted-by":"publisher","first-page":"2100","DOI":"10.1016\/j.disc.2016.03.003","volume":"339","author":"J Beier","year":"2016","unstructured":"Beier, J., Fierson, J., Haas, R., Russell, H.M., Shavo, K.: Classifying coloring graphs. Discrete Math. 339(8), 2100\u20132112 (2016). https:\/\/doi.org\/10.1016\/j.disc.2016.03.003. (0012\u2013365X, 1872\u2013681X)","journal-title":"Discrete Math."},{"key":"2938_CR7","doi-asserted-by":"publisher","unstructured":"Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map, Ann. of Math. (2), 14, 1-4, 42\u201346, https:\/\/doi.org\/10.2307\/1967597 1912\/13, 0003-486X,1939-8980","DOI":"10.2307\/1967597"},{"key":"2938_CR8","doi-asserted-by":"publisher","unstructured":"Bhakta, P., Krehbiel, S., Morris, R., Russell, H.M., Sathe, A., Su, Wesley, X., Maxine, B.: symmetries in graph coloring reconfiguration systems, 2023, 0196-8858,1090-2074, Adv. in Appl. Math., 149, Paper No. 102556, 17, https:\/\/doi.org\/10.1016\/j.aam.2023.102556,","DOI":"10.1016\/j.aam.2023.102556"},{"key":"2938_CR9","doi-asserted-by":"publisher","unstructured":"Bollob\u00e1s, B.: Modern graph theory, Graduate Texts in Mathematics, Springer-Verlag, New York, 184, 0-387-98488-7, (1998) https:\/\/doi.org\/10.1007\/978-1-4612-0619-4,","DOI":"10.1007\/978-1-4612-0619-4"},{"issue":"5\u20136","key":"2938_CR10","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1016\/j.disc.2007.07.028","volume":"308","author":"L Cereceda","year":"2008","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discrete Math. 308(5\u20136), 913\u2013919 (2008). https:\/\/doi.org\/10.1016\/j.disc.2007.07.028. (0012\u2013365X, 1872\u2013681X)","journal-title":"Discrete Math."},{"key":"2938_CR11","doi-asserted-by":"crossref","unstructured":"Chao, C.Y., Whitehead, E.G., Jr.: On chromatic equivalence of graphs, 1978, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Math., Vol. 642, Springer, Berlin-New York, 121\u2013131,","DOI":"10.1007\/BFb0070369"},{"issue":"4","key":"2938_CR12","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1002\/rsa.20129","volume":"29","author":"M Dyer","year":"2006","unstructured":"Dyer, M., Flaxman, A.D., Frieze, A.M., Vigoda, E.: Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures Algorithms 29(4), 450\u2013465 (2006). https:\/\/doi.org\/10.1002\/rsa.20129. (1042\u20139832,1098\u20132418)","journal-title":"Random Structures Algorithms"},{"key":"2938_CR13","unstructured":"Erey, A.: An investigation on graph polynomials., PhD thesis, Halifax, Canada, (2015)"},{"issue":"1","key":"2938_CR14","doi-asserted-by":"publisher","first-page":"355","DOI":"10.3906\/mat-1807-200","volume":"43","author":"A Erey","year":"2019","unstructured":"Erey, A.: A broken cycle theorem for the restrained chromatic function. Turkish J. Math. 43(1), 355\u2013360 (2019). https:\/\/doi.org\/10.3906\/mat-1807-200. (1300\u20130098,1303\u20136149)","journal-title":"Turkish J. Math."},{"issue":"3","key":"2938_CR15","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.aam.2005.08.009","volume":"38","author":"R Ghrist","year":"2007","unstructured":"Ghrist, R., Peterson, V.: The geometry and topology of reconfiguration. Adv. Appl. Math. 38(3), 302\u2013323 (2007). https:\/\/doi.org\/10.1016\/j.aam.2005.08.009. (0196\u20138858,1090\u20132074)","journal-title":"Adv. Appl. Math."},{"issue":"3","key":"2938_CR16","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1023\/A:1011258714032","volume":"13","author":"David D Gebhard","year":"2001","unstructured":"Gebhard, David D., Sagan, Bruce E.: A chromatic symmetric function in noncommuting variables. J. Algebraic Combin. 13(3), 227\u2013255 (2001). https:\/\/doi.org\/10.1023\/A:1011258714032. (0925\u20139899,1572\u20139192)","journal-title":"J. Algebraic Combin."},{"issue":"3","key":"2938_CR17","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/s00373-013-1302-3","volume":"30","author":"R Haas","year":"2014","unstructured":"Haas, R., Seyffarth, K.: The $$k$$-dominating graph. Graphs Combin. 30(3), 609\u2013617 (2014). https:\/\/doi.org\/10.1007\/s00373-013-1302-3. (0911\u20130119,1435\u20135914)","journal-title":"Graphs Combin."},{"key":"2938_CR18","doi-asserted-by":"publisher","unstructured":"Hogan, E., Scott, A., Tamitegama, Y., Tan, J.: A note on graphs of $$k$$-colourings, 2024, 1077\u20138926, Electron. J. Combin., 31, 4, Paper No. 4.48, 9, https:\/\/doi.org\/10.37236\/12853","DOI":"10.37236\/12853"},{"key":"2938_CR19","doi-asserted-by":"publisher","unstructured":"\u0141 azuka, E.: On chromaticity of graphs Discuss. Math. Graph Theory 15(1), 19\u201331 (1995). https:\/\/doi.org\/10.7151\/dmgt.1003 1234\u20133099,2083\u20135892","DOI":"10.7151\/dmgt.1003"},{"issue":"3","key":"2938_CR20","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/S0097539702401786","volume":"33","author":"MG Molloy","year":"2004","unstructured":"Molloy, M.G.: The, dynamics on colorings of a graph with high girth and maximum degree. SIAM J. Comput. 33(3), 721\u2013737 (2004). https:\/\/doi.org\/10.1137\/S0097539702401786. (0097\u20135397,1095\u20137111)","journal-title":"SIAM J. Comput."},{"key":"2938_CR21","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/S0021-9800(68)80087-0","volume":"4","author":"RC Read","year":"1968","unstructured":"Read, R.C.: An introduction to chromatic polynomials. J. Combinatorial Theory 4, 52\u201371 (1968). (0021\u20139800)","journal-title":"J. Combinatorial Theory"},{"key":"2938_CR22","doi-asserted-by":"publisher","unstructured":"Sagan, B.E.: Combinatorics: the art of counting, Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2020, 210, 978-1-4704-6032-7, https:\/\/doi.org\/10.1090\/gsm\/210,","DOI":"10.1090\/gsm\/210"},{"key":"2938_CR23","doi-asserted-by":"crossref","unstructured":"Schwenk, A.J.: Spectral reconstruction problems, 1979, Topics in graph theory (New York, 1977), Ann. New York Acad. Sci., 328, New York Acad. Sci., New York, 183\u2013189,","DOI":"10.1111\/j.1749-6632.1979.tb17779.x"},{"issue":"1","key":"2938_CR24","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/aima.1995.1020","volume":"111","author":"RP Stanley","year":"1995","unstructured":"Stanley, R.P.: A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math. 111(1), 166\u2013194 (1995). https:\/\/doi.org\/10.1006\/aima.1995.1020. (0001\u20138708,1090\u20132082)","journal-title":"Adv. Math."},{"key":"2938_CR25","doi-asserted-by":"crossref","unstructured":"Tutte, W.T.: A contribution to the theory of chromatic polynomials, 1954, Canadian Journal of Mathematics, 6, 80\u201391,","DOI":"10.4153\/CJM-1954-010-9"},{"key":"2938_CR26","doi-asserted-by":"publisher","unstructured":"Vigoda, E.: Improved bounds for sampling colorings, https:\/\/doi.org\/10.1063\/1.533196, Probabilistic techniques in equilibrium and nonequilibrium statistical physics 2000, 41, 1555\u20131569,","DOI":"10.1063\/1.533196"},{"issue":"8","key":"2938_CR27","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1090\/S0002-9904-1932-05460-X","volume":"38","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: A logical expansion in mathematics. Bull. Amer. Math. Soc. 38(8), 572\u2013579 (1932). https:\/\/doi.org\/10.1090\/S0002-9904-1932-05460-X. (0002\u20139904)","journal-title":"Bull. Amer. Math. Soc."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02938-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02938-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02938-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T06:25:05Z","timestamp":1757226305000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02938-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["2938"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02938-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,12]]},"assertion":[{"value":"22 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"82"}}