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

• Autorzy: Sakib A. Mondal
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

3-coloring; planar graph; discharging

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 4
• Strony: 775-789

Daty

wydano

2011

otrzymano

2010-04-05

zaakceptowano

2010-11-26

Twórcy

autor

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1579