A three and five color theorem

Author:
Frank R. Bernhart

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a face of a plane graph . The Three and Five Color Theorem proved here states that the vertices of can be colored with five colors, and using at most three colors on the boundary of . 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.

**[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*-*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*-*colour theorem for planar graphs*, Bull. London Math. Soc.**5**(1973), 302-306. MR**0323604 (48:1960)**

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

Retrieve articles in all journals with MSC: 05C15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1975-0373944-2

Article copyright:
© Copyright 1975
American Mathematical Society