A three and five color theorem
HTML articles powered by AMS MathViewer
- by Frank R. Bernhart PDF
- Proc. Amer. Math. Soc. 52 (1975), 493-498 Request permission
Abstract:
Let $f$ be a face of a plane graph $G$. The Three and Five Color Theorem proved here states that the vertices of $G$ can be colored with five colors, and using at most three colors on the boundary of $f$. With this result the well-known Five Color Theorem for planar graphs can be strengthened, and a relative coloring conjecture of Kainen can be settled except for a single case which happens to be a paraphrase of the Four Color Conjecture. Some conjectures are presented which are intermediate in strength to the Four Color Conjecture and the Three and Five Color Theorem.References
- Paul C. Kainen, Relative colorings of graphs, J. Combinatorial Theory Ser. B 14 (1973), 259–262. MR 316292, DOI 10.1016/0095-8956(73)90009-9
- Paul C. Kainen, A generalization of the $5$-color theorem, Proc. Amer. Math. Soc. 45 (1974), 450–453. MR 345861, DOI 10.1090/S0002-9939-1974-0345861-4
- Roy B. Levow, Relative colorings and the four-color conjecture, Amer. Math. Monthly 81 (1974), 491–492. MR 357201, DOI 10.2307/2318589
- Walter Meyer, Five-coloring planar maps, J. Combinatorial Theory Ser. B 13 (1972), 72–82. MR 307960, DOI 10.1016/0095-8956(72)90011-1
- A. J. W. Hilton, R. Rado, and S. H. Scott, A ($<5$)-colour theorem for planar graphs, Bull. London Math. Soc. 5 (1973), 302–306. MR 323604, DOI 10.1112/blms/5.3.302
Additional Information
- © Copyright 1975 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 52 (1975), 493-498
- MSC: Primary 05C15
- DOI: https://doi.org/10.1090/S0002-9939-1975-0373944-2
- MathSciNet review: 0373944