Wagner equivalence theorem

The equivalence set of Wagner , also known as equivalence theorem of K. Wagner or as Wagnerian equivalence theorem called, is a tenet of the mathematical branch of topological graph theory , which in 1937 by the mathematician Klaus Wagner published was. He makes a connection between the Hadwiger conjecture and the four-color problem .

Formulation of the sentence

The sentence can be stated as follows:

The four-color theorem is equivalent to the Hadwiger conjecture . ${\displaystyle (H_{5})}$

Comment on the classification of the result

According to the graph theorist Rudolf Halin , the equivalence theorem is a surprising result . It is the earliest attempt to "de-topologize" the four-color problem . In fact ... no reference is made to a flat representation in the formulation of . ... It [the four-color problem] also gave the impetus to express the general conjecture and examine it more closely ${\displaystyle (H_{5})}$ ${\displaystyle (H_{n})}$ .

Related result

In a communication presented in 1993, work has Neil Robertson , Paul Seymour and Robin Thomas showed that the Hadwiger's conjecture is also equivalent to the four color theorem. The restricted Hadwiger conjecture is thus secured. ${\displaystyle (H_{6})}$ ${\displaystyle (H_{n})\;(n\leq 6)}$

See also

• Wagner theorem
• Theorem by Wagner and Fáry

literature

• Reinhard Diestel : Graph Theory (=  Graduate Texts in Mathematics . Volume 173 ). 3. Edition. Springer Verlag , Berlin, Heidelberg, New York 2005, ISBN 3-540-26182-6 . MR2159259
• Rudolf Halin: Graph Theory I (=  yields of research . Volume 138 ). Scientific Book Society , Darmstadt 1980, ISBN 3-534-06767-3 . MR0586234
• N. Robertson , P. Seymour , R. Thomas :: Hadwiger's conjecture for -free graphs ${\displaystyle K_{6}}$ . In: Combinatorica . tape 13 , 1993, pp. 279-361 , doi : 10.1007 / BF01202354 ( springer.com ). MR1238823
• Klaus Wagner: About a property of the flat complexes . In: Mathematical Annals . tape 114 , 1937, pp. 570-590 ( springer.com ). MR1513158
• Klaus Wagner: Comments on Hadwinger's assumption . In: Mathematical Annals . tape 141 , 1960, pp. 433-451 ( springer.com ). MR0121309
• Klaus Wagner: Proof of a weakening of the Hadwiger conjecture . In: Mathematical Annals . tape 153 , 1964, pp. 139-141 ( springer.com ). MR0121309
• Klaus Wagner: Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut , Mannheim (inter alia) 1970, ISBN 3-411-00248-4 . MR0282850

References and footnotes

1. ^ Klaus Wagner: Graph theory. 1970, p. 148 ff., 171
2. ^ Rudolf Halin: Graphentheorie I. 1980, p. 268 ff., 274–275
3. ↑ Halin is a student of Klaus Wagner and has dedicated both volumes of his graph theory to him.
4. ↑ Halin, op.cit., P. 274
5. ^ N. Robertson et al .: Hadwiger's conjecture for -free graphs. ${\displaystyle K_{6}}$In: Combinatorica . 13 : pp. 279-361.