DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 31(4) (2011) 775-789
DOI: https://doi.org/10.7151/dmgt.1579

Planar graphs without 4-, 5- and 8-cycles are 3-colorable

Sakib A. Mondal

Enterprise Analytics Group
India Science Lab, General Motors Global Research and Development
GM Technical Centre India Pvt Ltd, Creator Bldg., International Tech Park Ltd.
Whitefield Road, Bangalore 560 066, INDIA

Abstract

In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.

Keywords: 3-coloring, planar graph, discharging

2010 Mathematics Subject Classification: 05C15.

References

[1]H.L. Abbott and B. Zhou, On small faces in 4-critical graphs, Ars Combin. 32 (1991) 203--207.
[2]O.V. Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory 21 (1996 ) 183--186, doi: 10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N.
[3]O.V. Borodin, To the paper: "On small faces in 4-critical graphs", Ars Combin. 43 (1996) 191--192.
[4]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. Combin. Theory (B) 93 (2005) 303--311, doi: 10.1016/j.jctb.2004.11.001.
[5]O.V. Borodin and A.N. Glebov, A sufficient condition for plane graphs to be 3-colorable, Diskret Analyz Issled. Oper. 10 (2004) 3--11.
[6]O.V. Borodin and A. Raspaud, A sufficient condition for planar graph to be 3-colorable, J. Combin. Theory (B) 88 (2003) 17--27, doi: 10.1016/S0095-8956(03)00025-X.
[7]O.V. Borodin, A.N. Glebov, M. Montassier and A. Raspaud, Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. Combin. Theory (B) 99 (2009) 668--673, doi: 10.1016/j.jctb.2008.11.001.
[8]M. Chen, A. Raspaud and W. Wang, Three-coloring planar graphs without short cycles, Information Processing Letters 101 (2007) 134--138, doi: 10.1016/j.ipl.2006.08.009.
[9]H. Grotsch, Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Mat.-Natur. Reihe 8 (1959) 102--120.
[10]I. Havel, On a conjecture of Grünbaum, J. Combin. Theory (B) 7 (1969)
184--186, doi: 10.1016/S0021-9800(69)80054-2.
[11]D.P. Sanders and Y. Zhao, A note on the three color problem, Graphs and Combin. 11 (1995) 91--94, doi: 10.1007/BF01787424.
[12]R. Steinberg, The state of the three color problem, in: Ouo Vadis, Graph Theory? 55 (1993) 211--248.
[13]W. Wang. and M. Chen, Planar graphs without 4,6,8-cycles are 3-colorable, Science in China Series A: Mathematics (Science in China Press, co-published with Springer-Verlag GmbH) 50 (2007) 1552--1562.
[14]L. Xiaofang, M. Chen and W. Wang, On 3-colorable planar graphs without cycles of four lengths, Information Processing Letters 103 (2007) 150--156, doi: 10.1016/j.ipl.2007.03.007.
[15]B.Xu, A 3-color theorem on plane graph without 5-circuits, Acta Mathematica Sinica 23 (2007) 1059--1062, doi: 10.1007/s10114-005-0851-7.
[16]L. Zhang and B. Wu, A note on 3-choosability of planar graphs without certain cycles, Discrete Math. 297 (2005) 206--209, doi: 10.1016/j.disc.2005.05.001.

Received 5 April 2010
Accepted 26 November 2010

Close