Counting Subgraphs of Coloring Graphs Using Shadow Graphs

Abstract 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.