On the degree-chromatic polynomial of a tree

Abstract

The degree chromatic polynomial $P_m(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has m adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.

Keywords

• chromatic polynomial
• graph coloring
• tree
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]