Counting Subgraphs of Coloring Graphs Using Shadow Graphs

Given a graph G , the k -coloring graph Cₖ(G) C k ( G ) is constructed by selecting proper k -colorings of G as vertices, with an edge between two colorings if they differ in the color of exactly one vertex. The number of vertices in Cₖ(G) C k ( G ) is the famous chromatic polynomial of G . Asgarli, Krehbiel, Levinson and Russell showed that for any subgraph H , the number of induced copies of H in Cₖ(G) C k ( G ) is a polynomial function in k . Hogan, Scott, Tamitegama, and Tan found a shorter proof for polynomiality of these chromatic H -polynomials. In this paper, we provide a method of constructing these polynomials explicitly in terms of chromatic polynomials of shadow graphs . We illustrate the practicality of our formulas by computing an explicit formula for H -polynomial for trees when H=Qd H = Q d is an arbitrary hypercube, a task which does not seem approachable from previous methods. The coefficients of the resulting polynomials feature generalized degree sequences introduced by Crew. In the special case when H is the complete graph on 2 vertices, the corresponding polynomial is dubbed the chromatic pairs polynomial . We present a pair of graphs G₁ G 1 and G₂ G 2 sharing the same chromatic pairs polynomial but different chromatic polynomials, disproving a conjecture raised by Asgarli, Krehbiel, Levinson and Russell.