On 1-improper 2-coloring of sparse graphs

A graph G is (1,1)-colorable if its vertices can be partitioned into subsets ^V1 and ^V2 such that every vertex in G[ ^Vi] has degree at most 1 for each iâ̂̂{1,2}. We prove that every graph with maximum average degree at most 145 is (1,1)-colorable. In particular, it follows that every planar graph with girth at least 7 is (1,1)-colorable. On the other hand, we construct graphs with maximum average degree arbitrarily close to 145 (from above) that are not (1,1)-colorable. In fact, we establish the best possible sufficient condition for the (1,1)-colorability of a graph G in terms of the minimum, ^ρG, of ^ρG(S)=7|S|-5|E(G[S])| over all subsets S of V(G). Namely, every graph G with ^ρG≥0 is (1,1)-colorable. On the other hand, we construct infinitely many non-(1,1)-colorable graphs G with ^ρG=- 1. This solves a related conjecture of Kurek and Ruciński from 1994.