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