Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs

A graph GG is (0,1)(0,1)-colorable   if V(G)V(G) can be partitioned into two sets V0V0 and V1V1 so that G[V0]G[V0] is an independent set and G[V1]G[V1] has maximum degree at most 1. The problem of verifying whether a graph is (0,1)(0,1)-colorable is NP-complete even in the class of planar graphs of girth 9.The maximum average degree  , mad(G), of a graph GG is the maximum of 2|E(H)||V(H)| over all subgraphs HH of GG. It was proved recently that every graph GG with mad(G)≤125 is (0,1)(0,1)-colorable, and this is sharp. This yields that every planar graph with girth at least 12 is (0,1)(0,1)-colorable.Let F(g)F(g) denote the supremum of aa such that for some constant bgbg every graph GG with girth gg and |E(H)|≤a|V(H)|+bg|E(H)|≤a|V(H)|+bg for every H⊆GH⊆G is (0,1)(0,1)-colorable. By the above, F(3)=1.2F(3)=1.2. We find the exact value for F(4)F(4) and F(5)F(5): F(4)=F(5)=119. In fact, we also find the best possible values of b4b4 and b5b5: every triangle-free graph GG with |E(H)|<11|V(H)|+59 for every H⊆GH⊆G is (0,1)(0,1)-colorable, and there are infinitely many not (0,1)(0,1)-colorable graphs GG with girth 5, |E(G)|=11|V(G)|+59 and |E(H)|<11|V(H)|+59 for every proper   subgraph HH of GG. A corollary of our result is that every planar graph of girth 11 is (0,1)(0,1)-colorable. This answers a half of a question by Dorbec, Kaiser, Montassier and Raspaud. In a companion paper, we show that for every gg, F(g)≤1.25F(g)≤1.25 and resolve some similar problems for the so-called (j,k)(j,k)-colorings   generalizing (0,1)(0,1)-colorings.