×

Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable. (English) Zbl 1327.05073

Summary: Let \(d_1, d_2, \ldots, d_k\) be \(k\) nonnegative integers. A graph \(G = (V, E)\) is \((d_1, d_2, \ldots, d_k)\)-colorable, if the vertex set \(V\) of \(G\) can be partitioned into subsets \(V_1, V_2, \ldots, V_k\) such that the subgraph \(G [V_i]\) induced by \(V_i\) has maximum degree at most \(d_i\) for \(i = 1, 2, \ldots, k\). R. Steinberg et al. [Holland. Ann. Discrete Math. 55, 211–248 (1993; Zbl 0791.05044)] conjectured that planar graphs without cycles of length 4 or 5 are \((0, 0, 0)\)-colorable. O. Hill et al. [Discrete Math. 313, No. 20, 2312–2317 (2013; Zbl 1281.05055)] showed that every planar graph without cycles of length 4 or 5 is \((3, 0, 0)\)-colorable. In this paper, we show that planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable. For further study in this direction, some problems and conjectures are presented.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbott, H. L.; Zhou, B., On small faces in 4-critical graphs, Ars Combin., 32, 203-207 (1991) · Zbl 0755.05062
[2] Appel, K.; Haken, W., Every planar map is four colorable, Part I. Discharging, Illinois J. Math., 21, 429-490 (1997) · Zbl 0387.05009
[3] Appel, K.; Haken, W., Every planar map is four colorable, Part II. Reducibility, Illinois J. Math., 21, 491-567 (1977) · Zbl 0387.05010
[4] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001
[5] Borodin, O. V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory, 21, 2, 183-186 (1996) · Zbl 0838.05039
[6] Borodin, O. V.; Glebov, A. N.; Raspaud, A.; Salavatipour, M. R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B, 93, 303-311 (2005) · Zbl 1056.05052
[7] Bu, Y.; Xu, J.; Wang, Y., \((1, 0, 0)\)-colorability of planar graphs without prescribed short cycles, J. Comb. Optim., 30, 627-646 (2015) · Zbl 1331.90061
[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] Grötzsch, H., Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel, Wiss Z Martin Luther Univ Halle-Wittenberg, Math-nat, 8, 109-120 (1959)
[11] Hill, O.; Smith, D.; Wang, Y.; Xu, L.; Yu, G., Planar graphs without 4-cycles or 5-cycles are \((3, 0, 0)\)-colorable, Discrete Math., 313, 2312-2317 (2013) · Zbl 1281.05055
[12] Hill, O.; Yu, G., A relaxation of Steinberg’s conjecture, SIAM J. Discrete Math., 27, 1, 584-596 (2013) · Zbl 1268.05074
[13] Li, H.; Xu, J.; Wang, Y., Planar graphs with cycles of length neither 4 nor 7 are \((3, 0, 0)\)-colorable, Discrete Math., 327, 29-35 (2014) · Zbl 1288.05094
[14] Lih, K.; Song, Z.; Wang, W.; Zhang, K., A note on list improper coloring planar graphs, Appl. Math. Lett., 14, 269-273 (2001) · Zbl 0978.05029
[15] Liu, P. P.; Wang, Y. Q., Planar graphs without cycles of length 4 or 7 are \((2, 0, 0)\)-colorable, Sci. Sin. Math., 44, 1153-1164 (2014), (in Chinese) · Zbl 1488.05139
[16] Sanders, D. P.; Zhao, Y., A note on the three coloring problem, Graphs Combin., 11, 91-94 (1995) · Zbl 0824.05023
[17] Steinberg, R., The state of the three color problem, (Gimbel, J.; Kenndy, J. W.; Quintas, L. V.; Vadis, Quo, Graph Theory. Graph Theory, Ann. Diserete Math., 55 (1993)), 211-248 · Zbl 0791.05044
[18] Wang, Y.; Jin, L.; Kang, Y., Planar graphs without cycles of length from 4 to 6 are \((1, 0, 0)\)-colorable, Sci. Sin. Math., 43, 1145-1164 (2013), (in Chinese) · Zbl 1488.05205
[19] Wang, Y.; Xu, L., Improper choosability of planar graphs without 4-cycles, SIAM J. Discrete Math., 27, 4, 2029-2037 (2013) · Zbl 1291.05077
[20] Wang, Y.; Xu, J., Planar graphs with cycles of length neither 4 nor 6 are \((2, 0, 0)\)-colorable, Inform. Process. Lett., 113, 659-663 (2013) · Zbl 1285.05071
[21] Wang, Y.; Xu, J., Improper colorability of planar graphs without prescribed short cycles, Discrete Math., 322, 5-14 (2014) · Zbl 1283.05114
[22] Wang, Y.; Xu, J., Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph, European J. Combin., 43, 98-123 (2015) · Zbl 1301.05273
[23] Wang, Y.; Yang, Y., \((1, 0, 0)\)-colorability of planar graphs with cycles of length 4, 5 or 9, Discrete Math., 326, 44-49 (2014) · Zbl 1288.05105
[24] Xu, B., On \((3, 1)^\ast \)-coloring of plane graphs, SIAM J. Discrete Math., 23, 1, 205-220 (2009)
[25] 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
[26] Xu, L.; Wang, Y., Improper colorability of planar graphs with cycles of length neither 4 nor 6, Sci. Sin. Math., 43, 1, 15-24 (2013), (in Chinese) · Zbl 1488.05206
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.