zbMATH — the first resource for mathematics

Near-colorings: non-colorable graphs and NP-completeness. (English) Zbl 1308.05052
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.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C07 Vertex degrees 05C35 Extremal problems in graph theory
Full Text: