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. 320324. ISSN 08939659
PDF Restricted to UT campus only: Request a copy 400Kb 
Abstract:  For positive integers and , a conditional coloring of a graph is a proper coloring of the vertices of such that every vertex of degree in is adjacent to vertices with at least different colors. The smallest integer for which a graph has a conditional coloring is called the thorder conditional chromatic number, and is denoted by . It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case ). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)colorability remains NPcomplete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the wellknown result that traditional 3colorability 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 treewidth. We also prove that some other wellknown 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