×

zbMATH — the first resource for mathematics

Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable. (English) Zbl 1327.05117
Summary: A \((c_1, c_2, \ldots, c_k)\)-coloring of \(G\) is a mapping \(\varphi : V(G) \mapsto \{1, 2, \ldots, k \}\) such that for every \(i\), \(1 \leq i \leq k\), \(G [V_i]\) has maximum degree at most \(c_i\), where \(G [V_i]\) denotes the subgraph induced by the vertices colored \(i\). O. V. Borodin and A. Raspaud [J. Comb. Theory, Ser. B 88, No. 1, 17–27 (2003; Zbl 1023.05046)] conjecture that every planar graph without 5-cycles and intersecting triangles is \((0, 0, 0)\)-colorable. We prove in this paper that such graphs are \((1, 1, 0)\)-colorable.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Borodin, O. V., Colorings of plane graphs: a survey, Discrete Math., 313, 517-539, (2013) · Zbl 1259.05042
[2] Borodin, O. V.; Glebov, A. N., A sufficient condition for planar graphs to be 3-colorable, Diskret Anal Issled Oper., 10, 3-11, (2004), (in Russian) · Zbl 1045.05041
[3] Borodin, O. V.; Glebov, A. N., Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable, J. Graph Theory, 66, 1-31, (2011) · Zbl 1237.05067
[4] Borodin, O. V.; Glebov, A. N.; Raspaud, A. R.; 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
[5] 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
[6] G. Chang, F. Havet, M. Montassier, A. Raspaud, Steinberg’s Conjecture and near colorings, manuscript.
[7] Z. Dvoˇrák, D. Král, R. Thomas, Coloring planar graphs with triangles far apart, Mathematics ArXiV, arXiv:0911.0885, 2009.
[8] Grötzsch, H., Ein dreifarbensatz für dreikreisfreienetze auf der kugel, Math.-Nat.Reihe, 8, 109-120, (1959)
[9] Havel, I., On a conjecture of grunbaum, J. Combin. Theory, Ser. B, 7, 184-186, (1969) · Zbl 0177.26805
[10] Hill, O.; Smith, D.; Wang, Y.; Xu, L.; Yu, G., Planar graphs without 4-cycles and 5-cycles are \((3, 0, 0)\)-colorable, Discrete Math., 313, 2312-2317, (2013) · Zbl 1281.05055
[11] Hill, O.; Yu, G., A relaxation of steinberg’s conjecture, SIAM J. Discrete Math., 27, 584-596, (2013) · Zbl 1268.05074
[12] Liu, R.; Li, X.; Yu, G., A relaxation of the Bordeaux conjecture, European J. Combin., 49, 240-249, (2015) · Zbl 1315.05059
[13] Steinberg, R., The state of the three color problem. quo vadis, graph theory?, Ann. Discrete Math., 55, 211-248, (1993)
[14] Xu, B., A 3-color theorem on plane graph without 5-circuits, Acta Math. Sin., 23, 1059-1062, (2007) · Zbl 1122.05038
[15] Xu, B., On \((3, 1)^\ast\)-coloring of planar graphs, SIAM J. Discrete Math., 23, 205-220, (2008)
[16] 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
[17] Xu, L.; Wang, Y., Improper colorability of planar graphs with cycles of length neither 4 nor 6 (in Chinese), Sci Sin Math, 43, 15-24, (2013)
[18] C. Yang, C. Yerger, The Bordeaux 3-color Conjecture and Near-Coloring, preprint.
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.