Accession Number:

AD0697922

Title:

SOME LABELING THEOREMS FOR PLANAR LINEAR GRAPHS: A CONTRIBUTION TO THE FOUR-COLOR PROBLEM.

Descriptive Note:

Final rept.,

Corporate Author:

NAVAL RESEARCH LAB WASHINGTON D C

Report Date:

1969-10-22

Pagination or Media Count:

48.0

Abstract:

According to Courant and Robbins, the four-color problem was probably proposed by Mobius in 1840. It was proposed again by De Morgan in 1850 and by Cayley in 1878. The problem may be stated as follows Given any linear graph which will map on a plane or sphere, it is possible to assign one of four colors to each face of the map so that no two faces colored alike have a common edge on their boundaries. In 1879 Kempe published a proof of the conjecture. However, in 1890, Heawood showed that Kempes proof was defective, by use of a counterexample that disproved one of Kempes assertions. The portion of this manuscript from Comment 18 through Lemma 24 is designed to take care of the analog to Heawoods counterexample. In the same paper, Heawood showed that five colors were sufficient to color a planar map. The problem has received much attention in the intervening years. Although a number of interesting results have been obtained since 1890, no one has been able to exhibit a planar graph that required more than four colors, nor has anyone been able to prove that four colors were sufficient in all cases. The situation up to now is summed up rather well by Courant and Robbins, Despite the efforts of many famous mathematicians, the matter essentially rests with this more modest result It has been proved that five colors suffice for all maps and it is conjectured that four will likewise suffice. This manuscript presents a new approach to and a partial proof of the conjecture. Author

Subject Categories:

  • Cartography and Aerial Photography
  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE