TY - JOUR

T1 - Improper coloring of sparse graphs with a given girth, I

T2 - (0,1)-colorings of triangle-free graphs

AU - Kim, Jaehoon

AU - Kostochka, Alexandr

AU - Zhu, Xuding

N1 - Funding Information:
The authors would like to thank anonymous referees for the helpful comments and suggestions. The research of the first author is partially supported by the Arnold O. Beckman Research Award of the University of Illinois at Urbana–Champaign. The research of the third author is supported by NSFC Grant 11171310 and ZJNSF Grant Z6110786 .

PY - 2014/11

Y1 - 2014/11

N2 - A graph G is (0, 1) -colorable if V (G) can be partitioned into two sets V0 and V1 so that G [V0] is an independent set and G [V1] 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)≤125 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)=119. In fact, we also find the best possible values of b4 and b5: every triangle-free graph G with |E(H)|<11|V(H)|+59 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)|+59 and |E(H)|<11|V(H)|+59 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.

AB - A graph G is (0, 1) -colorable if V (G) can be partitioned into two sets V0 and V1 so that G [V0] is an independent set and G [V1] 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)≤125 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)=119. In fact, we also find the best possible values of b4 and b5: every triangle-free graph G with |E(H)|<11|V(H)|+59 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)|+59 and |E(H)|<11|V(H)|+59 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.

UR - http://www.scopus.com/inward/record.url?scp=84902489215&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902489215&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2014.05.003

DO - 10.1016/j.ejc.2014.05.003

M3 - Article

AN - SCOPUS:84902489215

SN - 0195-6698

VL - 42

SP - 26

EP - 48

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -