On 11-improper 22-coloring of sparse graphs

A graph GG is (1,1)(1,1)-colorable if its vertices can be partitioned into subsets V1V1 and V2V2 such that every vertex in G[Vi]G[Vi] has degree at most 11 for each i∈{1,2}i∈{1,2}. We prove that every graph with maximum average degree at most 145 is (1,1)(1,1)-colorable. In particular, it follows that every planar graph with girth at least 77 is (1,1)(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)(1,1)-colorable.In fact, we establish the best possible sufficient condition for the (1,1)(1,1)-colorability of a graph GG in terms of the minimum, ρGρG, of ρG(S)=7|S|−5|E(G[S])|ρG(S)=7|S|−5|E(G[S])| over all subsets SS of V(G)V(G). Namely, every graph GG with ρG≥0ρG≥0 is (1,1)(1,1)-colorable. On the other hand, we construct infinitely many non-(1,1)(1,1)-colorable graphs GG with ρG=−1ρG=−1. This solves a related conjecture of Kurek and Ruciński from 1994.