On 3-colorings of Plane Graphs
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)