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

A graph G is ( 0 , 1 ) -colorable if V ( G ) can be partitioned into two sets V 0 and V 1 so that G [ V 0 ] is an independent set and G [ V 1 ] has maximum degree at most 1. The problem of verifying whether a graph is ( 0 , 1 ) -colorable is NP-complete even in the class of planar graphs of girth 9. ximum average degree, mad ( G ) , of a graph G is the maximum of 2 | E ( H ) | | V ( H ) | over all subgraphs H of G . It was proved recently that every graph G with mad ( G ) ≤ 12 5 is ( 0 , 1 ) -colorable, and this is sharp. This yields that every planar graph with girth at least 12 is ( 0 , 1 ) -colorable. ( g ) denote the supremum of a such that for some constant b g every graph G with girth g and | E ( H ) | ≤ a | V ( H ) | + b g for every H ⊆ G is ( 0 , 1 ) -colorable. By the above, F ( 3 ) = 1.2 . We find the exact value for F ( 4 ) and F ( 5 ) : F ( 4 ) = F ( 5 ) = 11 9 . In fact, we also find the best possible values of b 4 and b 5 : every triangle-free graph G with | E ( H ) | < 11 | V ( H ) | + 5 9 for every H ⊆ G is ( 0 , 1 ) -colorable, and there are infinitely many not ( 0 , 1 ) -colorable graphs G with girth 5, | E ( G ) | = 11 | V ( G ) | + 5 9 and | E ( H ) | < 11 | V ( H ) | + 5 9 for every proper subgraph H of G . A corollary of our result is that every planar graph of girth 11 is ( 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 g , F ( g ) ≤ 1.25 and resolve some similar problems for the so-called ( j , k ) -colorings generalizing ( 0 , 1 ) -colorings.