Klaus Wagner (b. 1937)
   HOME

TheInfoList



OR:

Klaus Wagner (March 31, 1910 – February 6, 2000) was a
German German(s) may refer to: * Germany (of or related to) **Germania (historical use) * Germans, citizens of Germany, people of German ancestry, or native speakers of the German language ** For citizens of Germany, see also German nationality law **Ger ...
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...
known for his contributions to
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
.


Education and career

Wagner studied
topology In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
at the
University of Cologne The University of Cologne (german: Universität zu Köln) is a university in Cologne, Germany. It was established in the year 1388 and is one of the most prestigious and research intensive universities in Germany. It was the sixth university to ...
under the supervision of who had been a student of
Issai Schur Issai Schur (10 January 1875 – 10 January 1941) was a Russian mathematician who worked in Germany for most of his life. He studied at the University of Berlin. He obtained his doctorate in 1901, became lecturer in 1903 and, after a stay at the ...
. Wagner received his Ph.D. in 1937, with a dissertation concerning the Jordan curve theorem and
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
, and taught at Cologne for many years himself. In 1970, he moved to the
University of Duisburg The old University of Duisburg was a university in Duisburg, Germany. History Its origins date back to the 1555 decision to create a university for the unified duchies at the Lower Rhine that were later to be merged into Prussia. After the foundati ...
, where he remained until his retirement in 1978.


Graph minors

Wagner is known for his contributions to
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
and particularly the theory of
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
s, graphs that can be formed from a larger graph by contracting and removing edges.
Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on fi ...
characterizes the
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s as exactly those graphs that do not have as a minor either a complete graph ''K''5 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 In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivi ...
, which states that the planar graphs are exactly those graphs that do not contain as a subgraph a
subdivision Subdivision may refer to: Arts and entertainment * Subdivision (metre), in music * ''Subdivision'' (film), 2009 * "Subdivision", an episode of ''Prison Break'' (season 2) * ''Subdivisions'' (EP), by Sinch, 2005 * "Subdivisions" (song), by Rus ...
of ''K''5 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''5 minor. This implies a characterization of the graphs with no ''K''5 minor as being constructed from planar graphs and
Wagner graph In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph. Properties As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, ...
(an eight-vertex Möbius ladder) by clique-sums, operations that glue together subgraphs at cliques of up to three vertices and then possibly remove edges from those cliques. This characterization was used by Wagner to show that the case ''k'' = 5 of the
Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...
on the chromatic number of ''Kk''-minor-free graphs is equivalent to the
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...
. Analogous characterizations of other families of graphs in terms of the summands of their clique-sum decompositions have since become standard in graph minor theory. Wagner conjectured in the 1930s (although this conjecture was not published until later) that in any infinite set of graphs, one graph is
isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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.


Recognition

Wagner was honored in 1990 by a
festschrift In academia, a ''Festschrift'' (; plural, ''Festschriften'' ) is a book honoring a respected person, especially an academic, and presented during their lifetime. It generally takes the form of an edited volume, containing contributions from the h ...
on graph theory, and in June 2000, following Wagner's death, the University of Cologne hosted a Festkolloquium in his memory.Festkolloquium in memoriam Klaus Wagner
/ref>


Selected publications

*.


References

{{DEFAULTSORT:Wagner, Klaus 1910 births 2000 deaths 20th-century German mathematicians Topologists Graph theorists