Klaus Wagner (mathematician)

Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician. He studied topology at the University of Cologne under the supervision of Karl Dörge, who had been a student of Issai Schur. Wagner received his Ph.D. in 1937, and taught at Cologne for many years himself. [mathgenealogy|name=Klaus Wagner|id=19958] In 1970, he moved to the University of Duisburg, where he remained until his retirement in 1978.

In June 2000, following Wagner's death, the University of Cologne hosted a Festkolloquium in his memory. [ [http://elib.zib.de/pub/opt-net/documents/v00w23n2 Conference announcement.] ]

Graph minors

Wagner is known for his contributions to graph theory and particularly the theory of graph minors.

Wagner's theorem characterizes the planar graphs as exactly those graphs that do not have as a minor either a complete graph "K"₅ on five vertices or a complete bipartite graph "K"_3,3 with three vertices on each side of its bipartition. That is, these two graphs are the only minor-minimal non-planar graphs. It is closely related to, but should be distinguished from, Kuratowski's theorem, which states that the planar graphs are exactly those graphs that do not contain as a subgraph a subdivision of "K"₅ or "K"_3,3.

Another result of his, also known as Wagner's Theorem, is that a four-connected graph is planar if and only if it has no "K"₅ minor. This implies a characterization of the graphs with no "K"₅ minor as being constructed from planar graphs and the eight-vertex Möbius ladder (sometimes called the "Wagner graph") by gluing together subgraphs at cliques of up to three vertices and then possibly removing edges from those cliques. This characterization was used by Wagner to show that the case "k" = 5 of the Hadwiger conjecture on the chromatic number of "K_k"-minor-free graphs is equivalent to the four color theorem. More complicated decompositions of graphs into clique-sums of simpler types of graphs, generalizing this result, have since become standard in graph minor theory.

Wagner conjectured in the 1930s (although this conjecture was not published until later) [citation|last=Casselman|first=Bill|title=Variations on Graph Minor|publisher=American Mathematical Society|url=http://www.ams.org/featurecolumn/archive/gminor.html.] that in any infinite set of graphs, one graph is isomorphic to a minor of another. The truth of this conjecture implies that any family of graphs closed under the operation of taking minors (as planar graphs are) can automatically be characterized by finitely many forbidden minors analogously to Wagner's theorem characterizing the planar graphs. Neil Robertson and Paul Seymour finally published a proof of Wagner's conjecture in 2004 and it is now known as the Robertson-Seymour theorem. [citation|last1=Robertson|first1=Neil|authorlink1=Neil Robertson (mathematician)|last2=Seymour|first2=Paul|authorlink2=Paul Seymour (mathematician)|title=Graph Minors XX: Wagner's Conjecture|journal=Journal of Combinatorial Theory, Series B|volume=92|year=2004|pages=325–357.]

References