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 N. For eachvertex v of the graph, r(v) is called the set of colors forbidden at v . A proper coloring of G is said to be permittedby 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 r(G; x) , is a function whose evaluations at integer x values count thenumber of proper x-colorings of the graph G permitted by the restraint r and this function is known to be a polynomialfunction of x for large enough x. The restrained chromatic function r(G; x) is a generalization of the well-knownchromatic polynomial (G; x) , as r(G; x) = (G; x) if r(v) = ∅ for each vertex v of the graph. Whitney’s celebratedbroken cycle theorem gives a combinatorial interpretation of the coefficients of the chromatic polynomial via certainsubgraphs (the so-called broken cycles). We provide an extension of this result by finding combinatorial interpretationsof the coefficients of the restrained chromatic function