Planar graphs without cycles of length from 4 to 7 are 3-colorable

Journal of Combinatorial Theory, Series B - Tập 93 - Trang 303-311 - 2005
O.V. Borodin1, A.N. Glebov1, A. Raspaud2, M.R. Salavatipour3
1Institute of Mathematics, Novosibirsk, 630090, Russia
2LaBRI, Université Bordeaux I, 33405 Talence Cedex, France
3Department of Computing Science, University of Alberta, Edmonton, Alta., Canada T6G 2E8

Tài liệu tham khảo

Abbott, 1991, On small faces in 4-critical graphs, Ars Combin., 32, 203 Borodin, 1979, To the paper of H.L. Abbott and B. Zhou on 4-critical planar graphs, Ars Combin., 25, 211 Borodin, 1996, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory, 21, 183, 10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N Jensen, 1995 Sanders, 1995, A note on the three color problem, Graphs Combin., 11, 91, 10.1007/BF01787424 R. Steinberg, The state of the three color problem, in: J. Gimbel, J.W. Kennedy, L.V. Quintas (Eds.), Quo Vadis, Graph Theory? Annals of Discrete Mathematics, vol. 55, 1993, pp. 211–248.