A broken cycle theorem for the restrained chromatic function

Abstract

A restraint $r$ on a graph $G$ is a function that assigns each vertex of the graph a finite subset of $\mathbb{N}$. For each vertex $v$ of the graph, $r(v)$ is called the set of colors forbidden at $v$. A proper coloring of $G$ is said to be permitted by a given restraint $r$ if each vertex $v$ of the graph receives a color that is not from its set of forbidden colors $r(v)$. The restrained chromatic function, denoted by $\pi_r(G,x)$, is a function whose evaluations at integer $x$ values count the number of proper $x$-colorings of the graph $G$ permitted by the restraint $r$ and this function is known to be a polynomial function of $x$ for large enough $x$. The restrained chromatic function $\pi_r(G,x)$ is a generalization of the well-known chromatic polynomial $\pi(G,x)$, as $\pi_r(G,x)=\pi(G,x)$ if $r(v)=\emptyset$ for each vertex $v$ of the graph. Whitney's celebrated broken cycle theorem gives a combinatorial interpretation of the coefficients of the chromatic polynomial via certain subgraphs (the so-called broken cycles). We provide an extension of this result by finding combinatorial interpretations of the coefficients of the restrained chromatic function.