zbMATH — the first resource for mathematics

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles. (English) Zbl 1388.05072
Summary: A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define \(V_i := \{v \in V(G) : c(v) = i \}\) for \(i = 1\) and 2. We say that \(G\) is \((d_1, d_2)\)-colorable if \(G\) has a 2-coloring such that \(V_i\) is an empty set or the induced subgraph \(G [V_i]\) has the maximum degree at most \(d_i\) for \(i = 1\) and 2. Let \(G\) be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether \(G\) is \((0, k)\)-colorable is NP-complete for every positive integer \(k\). Moreover, we construct non-\((1, k)\)-colorable planar graphs without 4-cycles and 5-cycles for every positive integer \(k\). In contrast, we prove that \(G\) is \((d_1, d_2)\)-colorable where \((d_1, d_2) = (4, 4),(3, 5),\) and \((2, 9)\).

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI arXiv
[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-561, (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, 83-93, (2010) · Zbl 1209.05177
[4] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80, (2014) · Zbl 1282.05041
[5] Chen, M.; Wang, Y.; Liu, P.; Xu, J., Planar graphs without cycles of length \(4\) or \(5\) are \((2, 0, 0)\)-colorable, Discrete Math., 339, 661-667, (2016)
[6] Choi, H.; Choi, I.; Jeong, J.; Suh, G., \((1, k)\)-coloring of graphs with girth at least \(5\) on a surface, J. Graph Theory, 84, 4, 521-535, (2017) · Zbl 1359.05099
[7] Choi, I.; Raspaud, A., Planar graphs with minimum cycle length at least \(5\) are \((3, 5)\)-colorable, Discrete Math., 338, 4, 661-667, (2015) · Zbl 1305.05072
[8] Cohen-Addad, V.; Hebdige, M.; Král, D.; Li, Z.; Salgado, E., Steinberg’s conjecture is false, J. Combin. Theory Ser. B, (2016), Available Online 26 July · Zbl 1350.05018
[9] 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, 187-195, (1986) · Zbl 0596.05024
[10] Eaton, N.; Hull, T., Defective List colorings of planar graphs, Bull. Inst. Combin. Appl., 25, 9-87, (1999) · Zbl 0916.05026
[11] Grötzsch, H., Zur theorie der diskreten gebilde. VII ein dreifarbensatz für dreikreisfreie netze auf der kugel, (Wiss. Z Martin-Luther-Univ. Halle-Wittenberg, Math.-Nat. Reihe, vol. 8, (1958/1959)), 109-120, (in German)
[12] Havet, F.; Sereni, J.-S., Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 181-199, (2006) · Zbl 1104.05026
[13] Montassier, M.; Ochem, P., Near-colorings: non-colorable graphs and NP-completeness, Electron. J. Combin., 22, 1, 13, (2015), Paper 157 · Zbl 1308.05052
[14] Xu, L.; Miao, Z.; Wang, Y., Every planar graph with cycles of length neither \(4\) nor \(5\) is \((1, 1, 0)\)-colorable, J. Comb. Optim., 28, 774-786, (2014) · Zbl 1309.05058
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.