A sufficient condition for planar graphs to be 3-colorable

Journal of Combinatorial Theory, Series B - Tập 88 - Trang 17-27 - 2003
O.V Borodin1, A Raspaud1
1LaBRI, Université Bordeaux I, 33405 Talence Cedex, France

Tài liệu tham khảo

Garey, 1976, Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, 10.1016/0304-3975(76)90059-1 Grötzsch, 1959, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin Luther Univ. Halle Wittenberg, Math.-Nat. Reihe, 8, 109 Havel, 1969, On a conjecture of B. Grünbaum, J. Combin. Theory, 7, 184, 10.1016/S0021-9800(69)80054-2 Jensen, 1995 R. Steinberg, The state of the three color problem, in: J. Gimbel, J.W. Kennedy, L.V. Quintas (Eds.), Quo Vadis, Graph Theory? Ann. Discrete Math. 55 (1993) 211–248.