Defective chromatic polynomials

Abstract

For a graph $G$ and an integer $d\ge 0$, the defective chromatic polynomial $\ddot{I}{‡}_d(G;k)$ counts the $k$-colorings of $G$ in which each vertex has at most $d$ neighbors of its own color. We investigate which structural properties of $G$ are determined by the full family $\{\ddot{I}{‡}_d(G;k){\}}_{d\ge 0}$. We establish a contraction formula expressing $\ddot{I}{‡}_d(G;k)$ as a sum of ordinary chromatic polynomials of the edge contractions of $G$. As a first application, we prove that for triangle-free graphs, the full family determines the degree sequence. For trees, we show further that the family $\{\ddot{I}{‡}_d(T;k){\}}_{d\ge 0}$ determines the path-subgraph counts $N(P_j,T)$ for $j=1,2,3,4$, but not for $j=5$. For each $n\ge 9$, we construct a pair of nonisomorphic trees of order $n$ that share the same defective chromatic polynomials for every $d\ge 0$.

17 pages