•  
  •  
 

Turkish Journal of Mathematics

Authors

AYSEL EREY

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.

First Page

355

Last Page

360

Included in

Mathematics Commons

Share

COinS