Counting Subgraphs of Coloring Graphs Using Shadow Graphs

Abstract Given a graph G , the k -coloring graph $$\mathcal {C}_k(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 $$\mathcal {C}_k(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 $$\mathcal {C}_k(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=Q_d$$ 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_1$$ G 1 and $$G_2$$ G 2 sharing the same chromatic pairs polynomial but different chromatic polynomials, disproving a conjecture raised by Asgarli, Krehbiel, Levinson and Russell.