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.

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