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 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(r)(G, x) if r(v) = empty set 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.