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. The maximum 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. Let F (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 trianglefree 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.
展开▼
