# Turkish Journal of Mathematics

## DOI

10.3906/mat-1807-200

## 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.

## Keywords

$x$-Coloring, restraint, chromatic polynomial, restrained chromatic function

## First Page

355

## Last Page

360

## Recommended Citation

EREY, AYSEL
(2019)
"A broken cycle theorem for the restrained chromatic function,"
*Turkish Journal of Mathematics*: Vol. 43:
No.
1, Article 28.
https://doi.org/10.3906/mat-1807-200

Available at:
https://journals.tubitak.gov.tr/math/vol43/iss1/28