On 3-colorings of Plane Graphs

Acta Mathematicae Applicatae Sinica, English Series - Tập 20 - Trang 597-604 - 2004
Bao-gang Xu1
1School of Math. & Computer Science, Nanjing Normal University, Nanjing, China

Tóm tắt

In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.

Tài liệu tham khảo

Alon, N., Tarsi, M. Colorings and orientations of graphs. Combinatorics, 12(2): 125–134 (1992) Bondy, J.A., Murty, U.S.R. Graph theory with applications. Macmillan Ltd. Press, New York, 1976 Borodin, O.V. Structural properties of plane graphs without adjacent triangles and an application to 3-colorings. Journal of Graph Theory, 21(2): 183–186 (1996) Borodin, O.V., Raspaud, A. A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, (Series. B), 88: 17–27 (2003) Borodin, O.V., Glebov, A.N., Raspaud, A., Salavatipour, M.R. Planar graphs without cycles of length from 4 to 7 are 3-colorable, manuscript. Havel, I. On a conjecture of B. Gr¨unbaum. Journal of Combinatorial Theory, 7: 184–186 (1969) Sanders, D.P., Zhao, Y. A note on the three color problem. Graphs and Combinatorics, 11: 91–94 (1995) Steinberg, R. The state of the three color problem, Quo Vadis. Graph Theory? J.Gimbel, J.W.Kennedy & L.V.Quintas (eds). Ann Discrete Math., 55: 211–248 (1993)