Improper coloring of sparse graphs with a given girth, I: (0, 1)-colorings of triangle-free graphs
Improper coloring of sparse graphs with a given girth, I: (0, 1)-colorings of triangle-free graphs
复制标题
DOI：
10.1016/j.ejc.2014.05.003
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Jaehoon Kim;A. Kostochka;Xuding Zhu
中科院分区：
文献类型：
--
作者：
Jaehoon Kim;A. Kostochka;Xuding Zhu
Abstract 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 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.
