Complexity of conditional colorability of graphs

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

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 264415