A 3-color Theorem on Plane Graphs without 5-circuits
Tóm tắt
In this paper, we prove that every plane graph without 5-circuits and without triangles of
distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O.
V., Raspaud, A.: A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial
Theory, Ser. B, 88, 17–27 (2003)], and provides a new upper bound to their conjecture.
Tài liệu tham khảo
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)
Abbott, H. L., Zhou, B.: On small faces in 4-critical graphs. Ars Combin., 32, 203–207 (1991)
Sanders, D. P., Zhao, Y.: A note on the three color problem. Graphs and Combinatorics, 11, 91–94 (1995)