Klaus Wagner

Klaus Wagner (a destra) e Frank Harary a Oberwolfach nel 1972.

Klaus Wagner (Colonia, 31 marzo 1910 – 6 febbraio 2000) è stato un matematico tedesco, noto per i suoi contributi alla teoria dei grafi.

Biografia

Wagner studiò topologia all'Università di Colonia sotto la direzione di Karl Dorge, che a sua volta era un ex allievo di Issai Schur. Nel 1937 conseguì il dottorato con una dissertazione sul teorema della curva di Jordan e il teorema dei quattro colori. Dopo aver insegnato a Colonia per vari anni, nel 1970 si trasferì all'Università di Duisburg, dove rimase fino al suo pensionamento nel 1978.

Teoria dei grafi minori

Il grafo di Wagner, una scala di Möbius a otto vertice che è generata dalla caratterizzazione di Wagner dei grafi privi di minori $K_{5}$ (completi su 5 vertici).

Wagner è noto per i suoi contributi alla teoria dei grafi e in particolare alla teoria dei grafi minori, che possono essere derivati da un grafo più esteso mediante contrazione o rimozione dei bordi. Il teorema di Wagner caratterizza i grafi planari come quei grafi per i quali non esiste un grafo minore minorenne né un grafo di tipo $K_{5}$ (cioè completo su cinque vertici) né un grafo bipartito completo di tipo $K_{3,3}$ (vale a dire con tre vertici su ciascun lato della sua bipartizione).
. In altre parole, questi due grafici sono gli unici grafici non planari minori minimali. Il Teorema di Wagner è strettamente correlato, ma dovrebbe essere distinto, dal teorema di Kuratowski, secondo il quale i grafi planari sono quelli che non contengono come un sottografo una partizione di $K_{5}$ o di $K_{3,3}$.

Un secondo importante risultato teorico, che è un corollario del Teorema di Wagner, afferma che un grafo connesso a 4 vertice è planare se e solo se non possiede un grafo minore di tipo $K_{5}$. Ciò implica una caratterizzazione dei grafi privi di minore $K_{5}$, come costruiti da grafi planari e da grafi di Wagner (ad esempio una scala di Möbius a otto vertici) "incollati" tra loro con una somma di cricche, un'operazione fra i grafi che prevede di incollare i sottografi fino a tre vertici con eventuale rimozione dei bordi dal relative cricche. Questa caratterizzazione fu utilizzata da Wagner per dimostrare che il teorema dei quattro colori è equivalente a un caso particolare (per $k=5$) della congettura di Hadwiger sul numero cromatico di un $K_{k}$-grafo (di tipo $K_{5}$) privo di sottografi minori. Dopo tale teorema, le caratterizzazioni di altre famiglie di grafi in termini di somme delle loro scomposizioni a cricca sono diventate uno standard nell'ambito teoria dei grafi minori.

Negli anni '30, Wagner congetturò che in qualsiasi insieme infinito di grafi esiste almeno un grafo isomorfo al grafo minore di un altro elemento dell'insieme. Se questa congettura fosse vera, ciò implicherebbe che qualsiasi operazione chiusa rispetto all'operazione di tracciamento di grafi minori (come sono ad esempio i grafi planari) può essere automaticamente caratterizzata da molti minori proibiti in modo analogo a quello in cui teorema di Wagner caratterizza i grafi planari.
La congettura fu resa pubblica molto tempo dopo, finché i matematici Neil Robertson e Paul Seymour riuscirono a dimostrarla nel 2004 con quello che fu chiamato il Teorema di Robertson-Seymour.

Premi e riconoscimenti

• 1990: festschrift sulla teoria dei grafi;
• 2000: festkolloquium postumo all'Università di Colonia.

Opere selezionate

• Wagner, K., Über eine Eigenschaft der ebenen Komplexe , in Mathematische Annalen, vol. 114, 1937, pp. 570–590, DOI:10.1007/BF01863196.

Bibliografia

• (EN) Rudolf Halin, Miscellaneous problems on infinite graphs, in Graph Theory, vol. 35, n. 2, Whiley, ottobre 2000, ISSN 0364-9024, OCLC 4640070745. Ospitato su archive.is. (doi: 10.1002/1097-0118(200010)35:2<128::AID-JGT6>3.0.CO;2-6)

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Klaus Wagner