×

zbMATH — the first resource for mathematics

The theorem on planar graphs. (English) Zbl 0585.01008
In 1930 K. Kuratowski published a proof of the ”Theorem on planar graphs”: A graph is planar if and only if it does not contain a subgraph homeomorphic to either \(K_ 5\) (the complete graph on 5 points), or \(K_{3,3}\) (the complete bipartite graph on 3,3 points). The authors tell the history of the discovery of the theorem and its proof, in which other mathematicians like O. Frink, P. A. Smith, L. S. Pontrjagin and K. Menger are involved. The authors clarify to what extent the attachment of Pontrjagin’s name to this theorem is justified.
Reviewer: H.K.Kaiser

MSC:
01A60 History of mathematics in the 20th century
05-03 History of combinatorics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aleksandrov, P.S; Hopf, H, ()
[2] Berge, C, (), Moscow, 1962
[3] Berman, G, Frequently cited publications in pure graph theory, Journal of graph theory, 1, 175-180, (1977), [MR 56#168; Zbl. 379.05019] · Zbl 0379.05019
[4] Biggs, N.L; Lloyd, E.K; Wilson, R.J, Graph theory 1736-1936, (1976), Oxford Univ. Press (Clarendon) London/New York, [MR 56#2771; Zbl 335.05101] · Zbl 0335.05101
[5] Bondy, J.A; Murty, U.S.R, Graph theory with applications, (1976), Elsevier North-Holland New York · Zbl 1134.05001
[6] Burstein, M, Kuratowski-Pontryagin theorem on planar graphs, Journal of combinatorial theory, ser. B, 14, 228-231, (1978), [MR 80h#05023; Zbl 383.05013] · Zbl 0383.05013
[7] Dirac, G.A; Schuster, S; Dirac, G.A; Schuster, S, A theorem of Kuratowski, Indagationes mathematicae, Indagationes mathematicae, 23, 360-348, (1961), [MR 26#6954] · Zbl 0098.36606
[8] Frankl, F; Pontryagin, L, Ein knotensatz anwendung auf die dimensiontheorie, Mathematische annalen, 102, 785-789, (1929) · JFM 56.0503.04
[9] Frink, O, A proof of Petersen’s theorem, Annals of mathematics, 27, 491-493, (1926) · JFM 52.0577.03
[10] Frink, O; Smith, P.A, Irreducible non-planar graphs, Bulletin of the American mathematical society, 36, 214, (1930) · JFM 56.0515.23
[11] Harary, F, (), Moscow: Izdatelstvo Mir, 1973 [MR 49#10586; Zbl 275.05101]
[12] Harary, F, Independent discoveries in graph theory, (), 1-4, [MR 81a:05001; Zbl 465.05026]
[13] Harary, F, Homage to the memory of kazimierz Kuratowski, Journal of graph theory, 5, 217-219, (1981) · Zbl 0459.05002
[14] Harary, F; Tutte, W.T, A dual form of Kuratowski’s theorem, Bulletin of the American mathematical society, 71, 168, (1965), [MR 32#8329] · Zbl 0127.39203
[15] Canadian Mathematical Bulletin{\bf8}, 17-20 [MR 32#8330]; Canadian Mathematical Bulletin{\bf8}, 373 [MR 32#8331]
[16] Kelmans, A.K, Graph expansion and reduction, (), 317-343, Szeged (Hungary) [MR 83e:05074] · Zbl 0475.05079
[17] Kelmans, A.K, The concept of a vertex in a matroid, the non-separating cycles and a new criterion for graph planarity, (), 345-388, Szeged (Hungary) [Zbl 494.05036] · Zbl 0494.05036
[18] Kelmans, A.K, Concept of a vertex in a matroid and 3-connected graphs, Journal of graph theory, 4, 13-19, (1980), [Zbl 416.05032] · Zbl 0416.05032
[19] Kelmans, A.K, A new planarity criterion for 3-connected graphs, Journal of graph theory, 5, 259-267, (1981), [MR 83a:05058; Zbl 416.05033, 457.05028] · Zbl 0416.05033
[20] Hudryavtsev, L.D, Some mathematical problems in electrical network theory, Uspekhi matematicheskikh nauk, novaya seriya, 3, No. 4, 80-118, (1948), [In Rusisan; MR 10.344a]
[21] Kuratowski, K, Sur LES courbes gauches, Annales polonici mathematici, 8, 324, (1929)
[22] Kuratowski, K; Kuratowski, K, Sur le problème des courbes gauches en topologie, (), 15, 1-13, (1930), [Note that the author’s name appeared as Casimir Kuratowski in the original.] This paper has also appeared in English translation in · JFM 56.1141.03
[23] Kuratowski, K, My personal recollections connected with the research on some topological problems, (), 43-47, [MR 55#5357: Zbl 355.01010]
[24] Kuratowski, K, Half a century of Polish mathematics, (1980), Pergamon Oxford · Zbl 0438.01006
[25] Menger, K, Zur allgemeinen kurventheorie, Fundamenta Mathematica, 10, 96-115, (1927) · JFM 53.0561.01
[26] Menger, K, Über plattbare dreiergraphen und die potenzen nichtplattbarer graphen, (), 67, 30-31, (1930), Also printed in · JFM 56.0514.06
[27] Menger, K, (), Reprinted, New York: Chelsea, 1967
[28] Menger, K, On the origin of the n-arc theorem, Journal of graph theory, 5, 341-350, (1981) · Zbl 0468.05050
[29] Roberts, F.S, Discrete mathematical models, (1976), Prentice-Hall Englewood Cliffs, N.J
[30] Schuster, S, Review of [burstein 1978], Mathematical reviews, (1980), MR 80h#05023
[31] Sheehan, J, Redfield discovered again, (), 135-155, Invited papers for the Ninth British Combinatorial Conference 1983 · Zbl 0517.05042
[32] Stemple, J.G, The four color problem, Papers in mathematics. annals of the New York Academy of sciences, 321, 91-101, (1979) · Zbl 0424.05024
[33] Thomassen, C, Kuratowski’s theorem, Journal of graph theory, 5, 225-241, (1981), [MR 83d#05039: Zbl 459.05035] · Zbl 0481.05023
[34] Turner, J; Kautz, W.H, A survey of progress in graph theory in the soviet union, Stanford, calif: Stanford research institute project 6885, (1968) · Zbl 0201.56702
[35] Turner, J; Turner, J, A survey of progress in graph theory in the soviet union, (), SIAM review, 12, iv-390, (1970), [MR 42#2973: Zbl 225.05101] · Zbl 0225.05101
[36] Urysohn, P, (), 1-172, 1. Section No. 4 13
[37] Wagner, K, Über eine erweiterung eines satzes von Kuratowski, Deutsche Mathematik, 2, 280-285, (1937), [Zbl 16.376] · JFM 63.0549.02
[38] Whitney, H, Planar graphs, Fundamenta Mathematica, 21, 73-84, (1933) · JFM 59.1235.03
[39] Wilson, R.J, (), Moscow: Izdatelstvo Mir, 1977 [Zbl 365.05022]
[40] Zykov, A.A, On some properties of linear complexes, Mathematicheskii sbornik, novaya seriya, American mathematical society translations, 79, 163-188, (1952), [MR 14#493a]
[41] Zykov, A.A, The theory of graphs, (), 188-223, 1963 [In Russian: MR 29#5235: Zbl 151.338]
[42] Zykov, A.A, Theory of finite graphs, (1969), Izdatelstvo Nauka, Sibirskoe Otdelkenie Novosibirsk, [In Russian; MR 42#5847: Zbl 213.258-259] · Zbl 0213.25801
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.