Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A three and five color theorem

Author: Frank R. Bernhart
Journal: Proc. Amer. Math. Soc. 52 (1975), 493-498
MSC: Primary 05C15
MathSciNet review: 0373944
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Paul C. Kainen, Relative colorings of graphs, J. Combinatorial Theory Ser. B 14 (1973), 259-262. MR 47 #4840. MR 0316292 (47:4840)
  • [2] -, A generalization of the $ 5$-color theorem, Proc. Amer. Math. Soc. 45 (1974), 450-453. MR 0345861 (49:10591)
  • [3] Roy B. Levow, Relative colorings and the four-color conjecture, Amer. Math. Monthly 81 (1974), 491-492. MR 0357201 (50:9669)
  • [4] W. Meyer, Five-coloring planar maps, J. Combinatorial Theory Ser. B 13 (1972), 72-82. MR 46 #7075. MR 0307960 (46:7075)
  • [5] A. J. W. Hilton, R. Rado and S. H. Scott, A $ A( < 5)$-colour theorem for planar graphs, Bull. London Math. Soc. 5 (1973), 302-306. MR 0323604 (48:1960)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C15

Retrieve articles in all journals with MSC: 05C15

Additional Information

Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society