zbMATH — the first resource for mathematics

Improper coloring of sparse graphs with a given girth. II: Constructions. (English) Zbl 1333.05115
Summary: A graph \(G\) is \((j,k)\)-colorable if \( V(G)\) can be partitioned into two sets \(V_j\) and \(V_k\) so that the maximum degree of \(G[V_j]\) is at most \(j\) and of \(G[V_k]\) is at most \(k\). While the problem of verifying whether a graph is \((0, 0)\)-colorable is easy, the similar problem with \((j,k)\) in place of \((0, 0)\) is NP-complete for all nonnegative \(j\) and \(k\) with \(j+k\geq1\). Let \(F_{j,k}(g)\) denote the supremum of all \(x\) such that for some constant \(c_g\) every graph \(G\) with girth \(g\) and \(|E(H)|+c_g\) for every \(H\subseteq G\) is \((j,k)\)-colorable. It was proved recently that \(F_{0,1}(3) =1.2\). In a companion paper, we find the exact value \(F{0,1}(4)=F_{0,1}(5)=\frac{11}{9}\). In this article, we show that increasing \(g\) from \(5\) further on does not increase \(F_{0,1}(g)\leq1.25\) much. Our constructions show that for every \(g\), \(F_{0,1}(g)\leq1.25\). We also find exact values of \(F_{j,k}(g)\) for all \(g\) and all \(k\geq2j+2\).
For Part I see [the authors, Eur. J. Comb. 42, 26.-48 (2014; Zbl 1297.05083)].

05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
Full Text: DOI
[1] Borodin, Near-proper vertex 2-colorings of sparse graphs, Diskretn Anal Issled Oper 16 (2) pp 16– (2009) · Zbl 1249.05110
[2] Borodin, Vertex partitions of sparse graphs into an independent vertex set and subgraph of maximum degree at most one, Sibirsk Mat Zh 52 (5) pp 1004– (2011) · Zbl 1232.05073
[3] Borodin, Defective 2-colorings of sparse graphs, J Combin Theory B 104 pp 72– (2014) · Zbl 1282.05041 · doi:10.1016/j.jctb.2013.10.002
[4] Borodin, On 1-improper 2-coloring of sparse graphs, Discrete Math 313 pp 2638– (2013) · Zbl 1281.05060 · doi:10.1016/j.disc.2013.07.014
[5] Dorbec, Limits of near-coloring of sparse graphs, J Graph Theory 75 pp 191– (2014) · Zbl 1280.05040 · doi:10.1002/jgt.21731
[6] Erdos, On chromatic number of graphs and set-systems, Acta Math Acad Sci Hungar 17 pp 61– (1966) · Zbl 0151.33701 · doi:10.1007/BF02020444
[7] Esperet, A complexity dichotomy for the coloring of sparse graphs, J Graph Theory 73 pp 85– (2013) · Zbl 1264.05049 · doi:10.1002/jgt.21659
[8] Glebov, Path partitions of planar graphs, Sib Elektron Mat Izv 4 pp 450– (2007) · Zbl 1132.05315
[9] Havet, Improper choosability of graphs and maximum average degree, J Graph Theory 52 pp 181– (2006) · Zbl 1104.05026 · doi:10.1002/jgt.20155
[10] Kim, Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs, European J of Combin 42 pp 26– (2014) · Zbl 1297.05083 · doi:10.1016/j.ejc.2014.05.003
[11] Kurek, Globally sparse vertex-Ramsey graphs, J Graph Theory 18 pp 73– (1994) · Zbl 0790.05027 · doi:10.1002/jgt.3190180108
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.