Counting Subgraphs of Coloring Graphs Using Shadow Graphs

Given a graph G, the k-coloring graph Ck(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 Ck(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 Ck(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 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 G1 and G2 sharing the same chromatic pairs polynomial but different chromatic polynomials, disproving a conjecture raised by Asgarli, Krehbiel, Levinson and Russell.

Duke Scholars

Author Simon MacLean