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

*(English)*Zbl 1297.05083Summary: 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, \(\operatorname{mad}(G)\), of a graph \(G\) is the maximum of \(\frac{2 | E(H) |}{| V(H) |}\) over all subgraphs \(H\) of \(G\). It was proved recently that every graph \(G\) with \(\operatorname{mad}(G) \leq \frac{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) | \leq a | V(H) | + b_g\) for every \(H \subseteq 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) = \frac{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) | < \frac{11 | V(H) | + 5}{9}\) for every \(H \subseteq G\) is \((0, 1)\)-colorable, and there are infinitely many not \((0, 1)\)-colorable graphs \(G\) with girth 5, \(| E(G) | = \frac{11 | V(G) | + 5}{9}\) and \(| E(H) | < \frac{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 P. Dorbec et al. [J. Graph Theory 75, No. 2, 191–202 (2014; Zbl 1280.05040)]. In a companion paper, we show that for every \(g\), \(F(g) \leq 1.25\) and resolve some similar problems for the so-called \((j, k)\)-colorings generalizing \((0, 1)\)-colorings.

We find the exact value for \(F(4)\) and \(F(5)\): \(F(4) = F(5) = \frac{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) | < \frac{11 | V(H) | + 5}{9}\) for every \(H \subseteq G\) is \((0, 1)\)-colorable, and there are infinitely many not \((0, 1)\)-colorable graphs \(G\) with girth 5, \(| E(G) | = \frac{11 | V(G) | + 5}{9}\) and \(| E(H) | < \frac{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 P. Dorbec et al. [J. Graph Theory 75, No. 2, 191–202 (2014; Zbl 1280.05040)]. In a companion paper, we show that for every \(g\), \(F(g) \leq 1.25\) and resolve some similar problems for the so-called \((j, k)\)-colorings generalizing \((0, 1)\)-colorings.

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C42 | Density (toughness, etc.) |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C35 | Extremal problems in graph theory |

Full Text:
DOI

##### References:

[1] | Borodin, O. V.; Ivanova, A. O., Near-proper vertex 2-colorings of sparse graphs, Diskretn. Anal. Issled. Oper., J. Appl. Ind. Math., 4, 1, 21-23, (2010), Translated |

[2] | Borodin, O. V.; Kostochka, A. V., Vertex partitions of sparse graphs into an independent vertex set and subgraph of maximum degree at most one, Sibirsk. Mat. Zh., Sib. Math. J., 52, 5, 796-801, (2011), Translation · Zbl 1232.05073 |

[3] | Dorbec, P.; Kaiser, T.; Montassier, M.; Raspaud, A., Limits of near-coloring of sparse graphs, J. Graph Theory, (2014), in press · Zbl 1280.05040 |

[4] | Esperet, L.; Montassier, M.; Ochem, P.; Pinlou, A., A complexity dichotomy for the coloring of sparse graphs, J. Graph Theory, 73, 85-102, (2013) · Zbl 1264.05049 |

[5] | Glebov, A. N.; Zambalaeva, D. Zh., Path partitions of planar graphs, Sib. Elektron. Mat. Izv., 4, 450-459, (2007), (in Russian) · Zbl 1132.05315 |

[6] | J. Kim, A.V. Kostochka, X. Zhu, Improper coloring of sparse graphs with a given girth, II: Constructions, submitted for publication. · Zbl 1333.05115 |

[7] | Kurek, A.; Rucinâ€™ski, A., Globally sparse vertex-Ramsey graphs, J. Graph Theory, 18, 73-81, (1994) · Zbl 0790.05027 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.