•  
  •  
 

Turkish Journal of Mathematics

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.

Keywords

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

First Page

355

Last Page

360

Download

Included in

Mathematics Commons

Share

COinS