Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable. (English) Zbl 1437.05077

Liu, Jie; Lv, Jian-Bo

Bull. Malays. Math. Sci. Soc. (2) 43, No. 3, 2493-2507 (2020).

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

Keywords:

improper coloring; planar graph; discharging method

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