Complexity of the conditional colorability of graphs

Simple item page
dc.creatorLi, Xueliang
dc.creatorYao, Xiangmei
dc.creatorZhou, Wenli
dc.date2007-11-19
dc.date.accessioned2026-07-07T08:43:41Z
dc.date.available2026-07-07T08:43:41Z
dc.descriptionFor an integer $r>0$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to vertices with at least $min\{r, d(v)\}$ different colors. The smallest integer $k$ for which a graph $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number, denoted by $χ_r(G)$. It is easy to see that the conditional coloring is a generalization of the traditional vertex coloring for which $r=1$. In this paper, we consider the complexity of the conditional colorings of graphs. The main result is that the conditional $(3,2)$-colorability is $NP$-complete for triangle-free graphs with maximum degree at most 3, which is different from the old result that the traditional 3-colorability is polynomial solvable for graphs with maximum degree at most 3. This also implies that it is $NP$-complete to determine if a graph of maximum degree 3 is $(3,2)$- or $(4,2)$-colorable. Also we have proved that some old complexity results for traditional colorings still hold for the conditional colorings.
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/0711.2843
dc.identifierhttp://arxiv.org/abs/0711.2843
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/142399
dc.subjectDiscrete Mathematics
dc.subjectComputational Complexity
dc.subjectG.2.2; F.2.2
dc.titleComplexity of the conditional colorability of graphs
dc.typetext

Files

Collections

arXiv