Complexity of conditional colorability of graphs

Share/Save/Bookmark

Li, Xueliang and Yao, Xiangmei and Zhou, Wenli and Broersma, Hajo (2009) Complexity of conditional colorability of graphs. Applied Mathematics Letters, 22 (3). pp. 320-324. ISSN 0893-9659

[img]PDF
Restricted to UT campus only
: Request a copy
400Kb
Abstract:For positive integers $k$ and $r$, 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, and is denoted by $X_r(G)$. It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case $r=1$). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.

Item Type:Article
Copyright:© 2009 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/67841
Official URL:http://dx.doi.org/10.1016/j.aml.2008.04.003
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 264415