Near-colorings: non-colorable graphs and NP-completeness (Q2260631): Difference between revisions

Summary: A graph \(G\) is \((d_1,\dots,d_l)\)-colorable if the vertex set of \(G\) can be partitioned into subsets \(V_1,\dots ,V_l\) such that the graph \(G[V_i]\) induced by the vertices of \(V_i\) has maximum degree at most \(d_i\) for all \(1 \leq i \leq 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) \neq (0,0)\) and \(g\geq3\), 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 determine 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.