Abstract
A graph G is (d1,...,dl)-colorable if the vertex set of G can be partitioned into subsets V1 , . . . , Vl such that the graph G[Vi ] induced by the vertices of Vi has maximum degree at most di for all 1 ≤ i ≤ l. In this paper, we focus on complexity aspects of such colorings when l = 2, 3. More precisely, we prove that, for any fixed integers k, j, g with (k, j) ̸= (0, 0) and g ≥ 3, either every planar graph with girth at least g is (k,j)-colorable or it is NP-complete to determine whether a planar graph with girth at least g is (k,j)-colorable. Also, for any fixed integer k, it is NP-complete to deter- mine whether a planar graph that is either (0,0,0)-colorable or non-(k,k,1)-colorable is (0, 0, 0)-colorable. Additionally, we exhibit non-(3, 1)-colorable planar graphs with girth 5 and non-(2, 0)-colorable planar graphs with girth 7.