zbMATH — the first resource for mathematics

Planar graphs with girth at least 5 are \((3, 5)\)-colorable. (English) Zbl 1305.05072
Summary: A graph is \((d_1, \ldots, d_r)\)-colorable if its vertex set can be partitioned into \(r\) sets \(V_1, \ldots, V_r\) where the maximum degree of the graph induced by \(V_i\) is at most \(d_i\) for each \(i \in \{1, \ldots, r \}\). Let \(\mathcal{G}_g\) denote the class of planar graphs with minimum cycle length at least \(g\). We focus on graphs in \(\mathcal{G}_5\) since for any \(d_1\) and \(d_2\), M. Montassier and P. Ochem [“Near-colorings: non-colorable graphs and NP-completeness”, submitted] constructed graphs in \(\mathcal{G}_4\) that are not \((d_1, d_2)\)-colorable. It is known that graphs in \(\mathcal{G}_5\) are \((2, 6)\)-colorable and \((4, 4)\)-colorable, but not all of them are \((3, 1)\)-colorable. We prove that graphs in \(\mathcal{G}_5\) are \((3, 5)\)-colorable, leaving two interesting questions open: (1) Are graphs in \(\mathcal{G}_5\) also \((3, d_2)\)-colorable for some \(d_2 \in \{2, 3, 4 \}\)? (2) Are graphs in \(\mathcal{G}_5\) indeed \((d_1, d_2)\)-colorable for all \(d_1 + d_2 \geq 8\) where \(d_2 \geq d_1 \geq 1\)?

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Appel, K.; Haken, W., Every planar map is four colorable. I. discharging, Illinois J. Math., 21, 3, 429-490, (1977) · Zbl 0387.05009
[2] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. II. reducibility, Illinois J. Math., 21, 3, 491-567, (1977) · Zbl 0387.05010
[3] Borodin, O. V.; Ivanova, A. O.; Montassier, M.; Ochem, P.; Raspaud, A., Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\), J. Graph Theory, 65, 2, 83-93, (2010) · Zbl 1209.05177
[4] Borodin, O. V.; Kostochka, A. V., Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1, Sibirsk. Mat. Zh., 52, 5, 1004-1010, (2011) · Zbl 1232.05073
[5] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80, (2014) · Zbl 1282.05041
[6] Borodin, O. V.; Kostochka, A.; Yancey, M., On 1-improper 2-coloring of sparse graphs, Discrete Math., 313, 22, 2638-2649, (2013) · Zbl 1281.05060
[7] Cowen, L. J.; Cowen, R. H.; Woodall, D. R., Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10, 2, 187-195, (1986) · Zbl 0596.05024
[8] Eaton, N.; Hull, T., Defective List colorings of planar graphs, Bull. Inst. Combin. Appl., 25, 9-87, (1999) · Zbl 0916.05026
[9] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 3, 181-199, (2006) · Zbl 1104.05026
[10] M. Montassier, P. Ochem, Near-colorings: non-colorable graphs and np-completeness, 2013, submitted for publication. · Zbl 1308.05052
[11] Škrekovski, R., List improper colourings of planar graphs, Combin. Probab. Comput., 8, 3, 293-299, (1999) · Zbl 0940.05031
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.