A broken cycle theorem for the restrained chromatic function

Authors : Aysel EREY

Pages : 355-360

View : 14 | Download : 8

Publication Date : 0000-00-00

Article Type : Research Paper

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, $rinsert ignore into journalissuearticles values(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 $rinsert ignore into journalissuearticles values(v);$. The restrained chromatic function, denoted by $\pi_rinsert ignore into journalissuearticles values(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_rinsert ignore into journalissuearticles values(G,x);$ is a generalization of the well-known chromatic polynomial $\piinsert ignore into journalissuearticles values(G,x);$, as $\pi_rinsert ignore into journalissuearticles values(G,x);=\piinsert ignore into journalissuearticles values(G,x);$ if $rinsert ignore into journalissuearticles values(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 insert ignore into journalissuearticles values(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