A broken cycle theorem for the restrained chromatic function

A restraint r " role="presentation"> r r r on a graph G " role="presentation"> G G G is a function that assigns each vertex of the graph a finite subset of N " role="presentation"> ℕ N \mathbb{N} . For each vertex v " role="presentation"> v v v of the graph, r ( v ) " role="presentation"> r ( v ) r ( v ) r(v) is called the set of colors forbidden at v " role="presentation"> v v v . A proper coloring of G " role="presentation"> G G G is said to be permitted by a given restraint r " role="presentation"> r r r if each vertex v " role="presentation"> v v v of the graph receives a color that is not from its set of forbidden colors r ( v ) " role="presentation"> r ( v ) r ( v ) r(v) . The restrained chromatic function, denoted by π r ( G , x ) " role="presentation"> π r ( G , x ) π r ( G , x ) \pi_r(G,x) , is a function whose evaluations at integer x " role="presentation"> x x x values count the number of proper x " role="presentation"> x x x -colorings of the graph G " role="presentation"> G G G permitted by the restraint r " role="presentation"> r r r and this function is known to be a polynomial function of x " role="presentation"> x x x for large enough x " role="presentation"> x x x . The restrained chromatic function π r ( G , x ) " role="presentation"> π r ( G , x ) π r ( G , x ) \pi_r(G,x) is a generalization of the well-known chromatic polynomial π ( G , x ) " role="presentation"> π ( G , x ) π ( G , x ) \pi(G,x) , as π r ( G , x ) = π ( G , x ) " role="presentation"> π r ( G , x ) = π ( G , x ) π r ( G , x ) = π ( G , x ) \pi_r(G,x)=\pi(G,x) if r ( v ) = ∅ " role="presentation"> r ( v ) = ∅ r ( v ) = ∅ r(v)=\emptyset for each vertex v " role="presentation"> v v 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.