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

Personal Author(s) : Trent,Horace M. ; Lepson,B. ; Hauptman,H. A.

Report Date : 22 OCT 1969

Pagination or Media Count : 48

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 Kempe's proof was defective, by use of a counterexample that disproved one of Kempe's assertions. The portion of this manuscript from Comment 18 through Lemma 24 is designed to take care of the analog to Heawood's 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)

Descriptors :   (*MAPS, COLORS), (*GRAPHICS, THEOREMS), POLYNOMIALS, SPHERES

Subject Categories : Cartography and Aerial Photography
      Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE