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

Jaehoon Kim, Alexandr Kostochka, Xuding Zhu

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)26-48
Number of pages23
JournalEuropean Journal of Combinatorics
StatePublished - Nov 2014

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs'. Together they form a unique fingerprint.

Cite this