Counting Subgraphs of Coloring Graphs Using Shadow Graphs

Abstract Given a graph G , the k -coloring graph $$\mathcal {C}_k(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>d</mml:mi> </mml:msub> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>G</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> and $$G_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>G</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> sharing the same chromatic pairs polynomial but different chromatic polynomials, disproving a conjecture raised by Asgarli, Krehbiel, Levinson and Russell.