PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 4 | 775-789
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
31
Numer
4
Strony
775-789
Opis fizyczny
Daty
wydano
2011
otrzymano
2010-04-05
zaakceptowano
2010-11-26
Twórcy
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1579
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.