Complexity of conditional colorability of graphs

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 χ 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.