Complexity of conditional colorability of graphs

For positive integers kk and rr, a conditional (k,r)(k,r)-coloring of a graph GG is a proper kk-coloring of the vertices of GG such that every vertex vv of degree d(v)d(v) in GG is adjacent to vertices with at least min{r,d(v)}min{r,d(v)} different colors. The smallest integer kk for which a graph GG has a conditional (k,r)(k,r)-coloring is called the rrth-order conditional chromatic number, and is denoted by χr(G)χr(G). It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case r=1r=1). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)(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)(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.