# zbMATH — the first resource for mathematics

Near-proper vertex 2-colorings of sparse graphs. (Russian) Zbl 1249.05110
Summary: A graph $$G$$ is $$(2, 1)$$-colorable if its vertices can be partitioned into subsets $$V_1$$ and $$V_2$$ such that each component in $$G[V_1]$$ contains at most two vertices while $$G[V_2]$$ is edgeless. We prove that every graph with maximum average degree $$\text{mad\,}(G) < 7/3$$ is $$(2, 1)$$-colorable. It follows that every planar graph with girth at least 14 is $$(2, 1)$$-colorable. We also construct a planar graph $$G_n$$ with $$\text{mad\,}(G_n)=(18n-2)/(7n-1)$$ that is not $$(2, 1)$$-colorable.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C07 Vertex degrees