×

zbMATH — the first resource for mathematics

Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable. (English) Zbl 1437.05077
Summary: A graph is \((d_1,\ldots ,d_r)\)-colorable if the vertex set can be partitioned into \(r\) sets \(V_1,\ldots ,V_r\) where the maximum degree of the subgraph induced by \(V_i\) is at most \(d_i\) for each \(i\in \{1,\ldots ,r\}\). In this paper, we prove that every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable, which improves the result of P. Sittitrai and K. Nakprasit [Discrete Math. 341, No. 8, 2142–2150 (2018; Zbl 1388.05072)], who proved that every planar graph without 4-cycles and 5-cycles is \((2, 9)\)-colorable.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borodin, OV; Ivanova, AO; 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
[2] Borodin, OV; Kostochka, AV, Defective 2-coloring of sparse graphs, J. Comb. Theory Ser. B, 104, 72-80 (2014) · Zbl 1282.05041
[3] 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, 2, 886-905 (2016) · Zbl 1327.05073
[4] Choi, I.; Raspaud, A., Planar graphs with girth at least 5 are (3, 5)-colorable, Discrete Math., 338, 4, 661-667 (2015) · Zbl 1305.05072
[5] Choi, H.; Choi, I.; Jeong, J.; Suh, G., \((1, k)\)-coloring of graphs with girth at least five on a surface, J. Graph Theory, 84, 4, 521-535 (2017) · Zbl 1359.05099
[6] Cowen, LJ; Cowen, RH; Woodall, DR, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10, 2, 187-195 (1986) · Zbl 0596.05024
[7] Eaton, N.; Hull, T., Defective list colorings of planar graphs, Bull. Inst. Comb. Appl., 25, 79-87, 40 (1999) · Zbl 0916.05026
[8] Havet, F.; Sereni, JS, Improper choosability of graphs and maximum average degree, J. Graph Theory, 52, 3, 181-199 (2006) · Zbl 1104.05026
[9] Kim, J.; Kostochka, A.; Zhu, X., Improper coloring of sparse graphs with a given girth, I:(0, 1)-colorings of triangle-free graphs, Eur. J. Comb., 42, 26-48 (2014) · Zbl 1297.05083
[10] Liu, R.; Li, X.; Yu, G., Planar graphs without 5-cycles and intersecting triangles are (1, 1, 0)-colorable, Discrete Math., 339, 2, 992-1003 (2016) · Zbl 1327.05117
[11] Montassier, M., Ochem, P.: Near-colorings: non-colorable graphs and NP-completeness. Electron. J. Comb. 22(1) , Paper 1.57,13 (2015) · Zbl 1308.05052
[12] Sittitrai, P.; Nakprasit, K., Defective 2-colorings of planar graphs without 4-cycles and 5-cycles, Discrete Math., 341, 8, 2142-2150 (2018) · Zbl 1388.05072
[13] 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, 4, 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.