Kempe Chains in the maximal planar graphs without an impasse

“A Picture is Worth a Thousand Words”

I. Cahit

Girne American University

Abstract. Historically the flaw in Kempe’s argument in the proof of the four color map problem of Francis Guthrie have been pointed out by Heawood (also by de la Vallée Poussin). Other bad examples have been provided by A. Errera in 1921 and by I. Kittell in 1935. Despite the similar proofs of the four color theorem with the aid of an computer in the last quarter of 20th century Kempe chain remain the essential tool in the possible non-computer proof of this famous theorem. In this note we have given four color of Heawood, Errera and Kittell graphs which are based on, respectively hamiltonian cycle and path in the dual graphs of these bad examples. Particularly we have introduced spiral chains of a maximal planar graph which enable us to color any maximal planar graph with four colors.

Figure 1: Four color of Errera graph without an impasse

Figure 2: Four color of Heawood graph without an impasse

Figure 3: Four color of Heawood graph using spiral chains.

Figure 4: Four color of Kittell graph by spiral chains.

Figure 5: Four color of MPG5 graphs by spiral chain.

Figure 6: Another Zoe graph with spiral chains.

Figure 7: Spiral Chain

References

[1] K. Appel and W. Haken, Every planar map is four colorable, Contemporary Math., 98 (1989).

[2] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, J. Combin. Theory Ser. B. 70 (1997), 2-44.

[3] J. P. Heawood, On the four-color map theorem, Quart. J. Pure Math., 29 (1898), 270-285.

[4] A. Errera, Du colorage de cartes et de quelques questions d’analysis situs, Thesis, Gauthier-Villars, Paris, 1921, 66 pp.

[5] I. Kitell, A group of operations on a partially colored map, Bull. Amer. Math. Soc., 41 1935, 407-413.

[5] S. Wagon, An April fool’s hoax, Mathematica in Education and Research, 7(1), 1998, 46-52.

[6] P. Rolland, Générer les triangulations de la sphère de degré minimum cinq sans répétition ni test d’isomorphism, Ph.D. thesis, Université de Nantes, 1997.

[7] J. P. Hutchinson and S. Wagon, Kempe revisited, Amer. Math. Monthly, 105 (1998), 170-174.

[8] D. Archdeacon, A picture is worth a thousand words: Topological graph theory, preprint, June 2001.

[9] http://www.math.gatech.edu/~thomas/FC/fourcolor.html

[10] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, A new proof of the four colour theorem, Electron.

Res. Announc. Amer. Math. Soc. 2 (1996), 17-25 (electronic).

© I. Cahit, October 24, 2003