×

zbMATH — the first resource for mathematics

A new proof of the 6 color theorem. (English) Zbl 0826.05027
The result reads: The vertices and faces of every plane graph can be colored with 6 colors so that any two adjacent or incident elements are colored differently.
This statement proved the author already in 1984 using a much larger number of reducible configurations, see [the author, Solution of Ringel’s problems concerning the vertex-faced coloring of planar graphs and coloring of 1-planar graphs, Metody Diskretn. Anal. 41, 12-26 (1984; Zbl 0565.05027)] and [G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hamb. 29, 107-117 (1965; Zbl 0132.207)].

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, Ill. J. Math. 20 pp 218– (1976)
[2] Archdeacon, Congres. Numer. 39 pp 89– (1983)
[3] Behzad, J. London Math. Soc. 42 pp 226– (1967)
[4] Bodendiek, Abh. Math. Sem. Univ. Hamburg 53 pp 41– (1983)
[5] Borodin, Met. discret. anal., Novosibirsk 41 pp 12– (1984)
[6] Borodin, Met. diskret. anal., Novosibirsk 43 pp 3– (1986)
[7] On cyclic coloring the vertices of plane graphs. Abstracts of the Ist World Congress of the Bernoulli Society. Tashkent (1986) 499 (in Russian).
[8] Borodin, Met. Diskret. anal. Novosibirsk 45 pp 21– (1987)
[9] Borodin, J. reine angew. Math. 394 pp 180– (1989)
[10] Jucovič, Mat. čas. 19 pp 225– (1969)
[11] Precise upper bound for the total chromatic number of multigraphs. 24th Internationales Wissenschaftliches. Kolloquium TH Ilmenau, Vortragsreihe ”Theorie der Graphen und Netzwerke” (1979) 33–36 (in Russian).
[12] Kronk, Discrete Math. 5 pp 253– (1973)
[13] Plummer, J. Graph Theory 11 pp 507– (1987)
[14] and , Cyclic coloration of planar graphs. Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968); Academic Press, New York-London (1969) 287–293.
[15] Ringel, Abh. Math. Sem. Univ. Hamburg 29 pp 107– (1965)
[16] A nine color theorem for the torus and the Klein bottle. The Theory and Applications of Graphs, Kalamazoo, 1980. Wiley, New York (1981) 507–515.
[17] Schumacher, Abh. Math. Sem. Univ. Hamburg 54 pp 5– (1984)
[18] Vizing, Uspehi mat. nauk 23 pp 117– (1968)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.