Near-proper vertex 2-colorings of sparse graphs. (Russian) Zbl 1249.05110

Borodin, O. V.; Ivanova, A. O.

Diskretn. Anal. Issled. Oper. 16, No. 2, 16-20 (2009).

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

Keywords:

planar graph; girth; coloring; partition; maximum average degree (MAD)