A three and five color theorem
Frank R. Bernhart · Proceedings of the American Mathematical Society · 1975
Let f f be a face of a plane graph G G . The Three and Five Color Theorem proved here states that the vertices of G G can be colored with five colors, and using at most three colors on the boundary of f 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.