×

zbMATH — the first resource for mathematics

Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable. (English) Zbl 1203.05048
Summary: It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable [O.V. Borodin, A.N. Glebov, A. Raspaud,and M.R. Salavatipour, “Planar graphs without cycles of length from 4 to 7 are 3-colorable,” J. Comb. Theory, Ser. B 93, No. 2, 303–311 (2005; Zbl 1056.05052)] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable [O.V. Borodin, A.N. Glebov, T.R. Jensen, and A. Raspaud,“Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable,” Sib. Elektron. Mat. Izv. 3, 428–440, electronic only (2006; Zbl 1119.05037)]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with \(k\)-cycles, where \(k \in \{ 4,5,7 \}\) (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
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] Aksenov, V.A., Chromatic connected vertices in planar graphs, Diskretn. analiz., 31, 5-16, (1977), (in Russian) · Zbl 0407.05033
[3] Aksenov, V.A.; Borodin, O.V.; Glebov, A.N., On extending 3-colorability from two vertices in a planar triangle-free graph, Diskretn. anal. issled. oper., 9, 1, 3-26, (2002), (in Russian) · Zbl 1008.05064
[4] Aksenov, V.A.; Borodin, O.V.; Glebov, A.N., On extending 3-colorability from a 6-face to a planar triangle-free graph, Diskretn. anal. issled. oper., 10, 3, 3-11, (2003), (in Russian) · Zbl 1047.05014
[5] Aksenov, V.A.; Borodin, O.V.; Glebov, A.N., Extending 3-colorability from a 7-face to a planar triangle-free graph, Sib. elektron. mat. izv., 1, 117-128, (2004), http://semr.math.nsc.ru (in Russian) · Zbl 1077.05039
[6] 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
[7] 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
[8] Borodin, O.V.; Glebov, A.N., A sufficient condition for plane graphs to be 3-colorable, Diskretn. anal. issled. oper., 10, 3, 3-11, (2004), (in Russian) · Zbl 1045.05041
[9] O.V. Borodin, A.N. Glebov, Planar graphs without 5-cycles and with minimal distance between triangles at least 2 are 3-colourable, J. Graph Theory (in press).
[10] Borodin, O.V.; Glebov, A.N., Decomposing planar graphs of girth 5 into an edgeless and acyclic subgraphs, Diskretn. anal. issled. oper., 8, 4, 34-53, (2001), (in Russian) · Zbl 1012.05133
[11] 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. elektron. mat. izv., 3, 428-440, (2006) · Zbl 1119.05037
[12] Borodin, O.V.; Glebov, A.N.; Montassier, M.; Raspaud, A., Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. combin. theory ser. B, 99, 668-673, (2009) · Zbl 1184.05024
[13] 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
[14] Borodin, O.V.; Montassier, M.; Raspaud, A., Planar graphs without adjacent cycles of length at most seven are 3-colorable, Discrete math., 310, 1, 167-173, (2010) · Zbl 1221.05071
[15] Borodin, O.V.; Raspaud, A., A sufficient condition for planar graphs to be 3-colorable, J. combin. theory ser. B, 88, 17-27, (2003) · Zbl 1023.05046
[16] Gimbel, J.; Thomassen, C., Coloring graphs with fixed genus and girth, Trans. amer. math. soc., 349, 4555-4564, (1997) · Zbl 0884.05039
[17] Grötzsch, H., Ein dreifarbenzatz für dreikreisfreie netze auf der kugel, Wiss. Z. martin-luther-univ. halle-Wittenberg math.-natur. reihe, 8, 109-120, (1959)
[18] Havel, I., On a conjecture of B. grünbaum, J. combin. theory ser. B, 7, 2, 184-186, (1969) · Zbl 0177.26805
[19] Havel, I., O zbarvitelnosti rovinných grafů třemi barvami, Math. geometrie a teorie grafů (praha), 89-91, (1970)
[20] Jensen, T.R.; Thomassen, C., The color space of a graph, J. graph theory, 34, 3, 234-245, (2000) · Zbl 0957.05036
[21] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley Interscience · Zbl 0971.05046
[22] Sanders, D.P.; Zhao, Y., A note on the three color problem, Graphs combin., 11, 91-94, (1995) · Zbl 0824.05023
[23] Steinberg, R.; Gimbel, J.; Kennedy, J.W.; Quintas, L.V., The state of the three color problem, Quo vadis, graph theory?, Annals of discrete math., 55, 211-248, (1993)
[24] Xu, B., On 3-colorable plane graphs without 5- and 7-cycles, J. combin. theory ser. B, 96, 958-963, (2006) · Zbl 1108.05046
[25] Xu, B., A 3-color theorem on plane graph without 5-circuits, Acta math. sinica, 23, 6, 1059-1062, (2007) · Zbl 1122.05038
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.