Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
Oleg Veniaminovich Borodin, Alexandr V. Kostochka · Siberian Mathematical Journal · 2011
A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V 1 and V 0 so that in G[V 1] every vertex has degree at most 1, while G[V 0] is edgeless. We prove that every graph with maximum average degree at most $\tfrac{{12}} {5} $ is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to $\tfrac{{12}} {5} $ which are not (1, 0)-colorable. In fact, we prove a stronger result by establishing the best possible sufficient condition for the (1, 0)-colorability of a graph G in terms of the minimum, Ms(G), of 6|V(A)| − 5|E(A)| over all subgraphs A of G. Namely, every graph G with Ms(G) ≥ −2 is proved to be (1, 0)-colorable, and we construct an infinite series of non-(1, 0)-colorable graphs G with Ms(G) = −3.