×

Planar graphs without adjacent cycles of length at most seven are 3-colorable. (English) Zbl 1221.05071

Summary: We prove that every planar graph in which no \(i\)-cycle is adjacent to a \(j\)-cycle whenever \(3\leq i\leq j\leq 7\) is 3-colorable and pose some related problems on the 3-colorability of planar graphs.

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] Aksionov, V. A.; Mel’nikov, L. S., Some counterexamples associated with the three color problem, J. Combin. Theory Ser. B, 28, 1-9 (1980) · Zbl 0434.05033
[3] Appel, K.; Haken, W., Every planar map is four colorable. Part I. Discharging, Illinois J. Math., 21, 429-490 (1977) · Zbl 0387.05009
[4] Appel, K.; Haken, W., Every planar map is four colorable. Part II. Reducibility, Illinois J. Math., 21, 491-567 (1977) · Zbl 0387.05010
[5] Borodin, O. V., To the paper of H.L. Abbott and B. Zhou on 4-critical planar graphs, Ars Combin., 43, 191-192 (1996) · Zbl 0881.05037
[6] 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
[7] Borodin, O. V.; Glebov, A. N., A sufficient condition for plane graphs to be 3-colorable, Diskret. analyz i issled. oper., 10, 3, 3-11 (2004), in Russian · Zbl 1045.05041
[8] O.V. Borodin, A.N. Glebov, Planar graphs without 5-cycles and with minimum distance between triangles at least two are 3-colorable, Manuscript, 2008; O.V. Borodin, A.N. Glebov, Planar graphs without 5-cycles and with minimum distance between triangles at least two are 3-colorable, Manuscript, 2008
[9] Borodin, O. V.; Glebov, A. N.; Jensen, T. R.; Raspaud, A., Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable, Sib. Electron. Mat. Reports, 3, 428-440 (2006) · Zbl 1119.05037
[10] 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
[11] Borodin, O. V.; Raspaud, A., A sufficient condition for planar graph to be 3-colorable, J. Combin. Theory Ser. B, 88, 17-27 (2003) · Zbl 1023.05046
[12] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[13] Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, Math.-Nat. Reihe, 8, 109-120 (1959)
[14] Havel, I., On a conjecture of Grünbaum, J. Combin. Theory Ser. B, 7, 184-186 (1969) · Zbl 0177.26805
[15] Havel, I., On a conjecture of B. Grünbaum, J. Combin. Theory Ser. B, 7, 184-186 (1969) · Zbl 0177.26805
[16] Havel, I., O zbarvitelnosti rovinnych grafů theremi barvami, (Math. Geometrie a theorie grafů (1970), Praha), 89-91
[17] Montassier, M.; Raspaud, A.; Wang, W.; Wang, Y., A relaxation of Havel’s 3-color problem, Inform. Process. Lett., 107, 3-4, 107-109 (2008) · Zbl 1185.05062
[18] Sanders, D. P.; Zhao, Y., A note on the three color problem, Graphs Combin., 11, 91-94 (1995) · Zbl 0824.05023
[19] Steinberg, R., The state of the three color problem, Quo Vadis, Graph Theory?. Quo Vadis, Graph Theory?, Ann. Discrete Math., 55, 211-248 (1993) · Zbl 0791.05044
[20] Xu, B., A 3-color theorem on plane graph without 5-circuits, Acta Math. Sinica, 23, 6, 1059-1062 (2007) · Zbl 1122.05038
[21] Zhang, L.; Wu, B., Three-coloring planar graphs without certain small cycles, Graph Theory Notes N.Y., 46, 27-30 (2004)
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.