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

Sakib A. Mondal

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 775-789
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Sakib A. Mondal. "Planar graphs without 4-, 5- and 8-cycles are 3-colorable." Discussiones Mathematicae Graph Theory 31.4 (2011): 775-789. <http://eudml.org/doc/270962>.

@article{SakibA2011,
abstract = {In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.},
author = {Sakib A. Mondal},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {3-coloring; planar graph; discharging},
language = {eng},
number = {4},
pages = {775-789},
title = {Planar graphs without 4-, 5- and 8-cycles are 3-colorable},
url = {http://eudml.org/doc/270962},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Sakib A. Mondal
TI - Planar graphs without 4-, 5- and 8-cycles are 3-colorable
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 775
EP - 789
AB - In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.
LA - eng
KW - 3-coloring; planar graph; discharging
UR - http://eudml.org/doc/270962
ER -

References

top
  1. [1] H.L. Abbott and B. Zhou, On small faces in 4-critical graphs, Ars Combin. 32 (1991) 203-207. Zbl0755.05062
  2. [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 Zbl0838.05039
  3. [3] O.V. Borodin, To the paper: 'On small faces in 4-critical graphs', Ars Combin. 43 (1996) 191-192. Zbl0881.05037
  4. [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. Zbl1056.05052
  5. [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. [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. Zbl1023.05046
  7. [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. Zbl1184.05024
  8. [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. Zbl1185.05057
  9. [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. [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. Zbl0177.26805
  11. [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. Zbl0824.05023
  12. [12] R. Steinberg, The state of the three color problem, in: Ouo Vadis, Graph Theory? 55 (1993) 211-248. Zbl0791.05044
  13. [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. Zbl1144.05033
  14. [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. Zbl1185.05061
  15. [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. Zbl1122.05038
  16. [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. Zbl1070.05046

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.