Klaus Wagner
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[1], nel 1970 si trasferì all'Università di Duisburg, dove rimase fino al suo pensionamento nel 1978.
Teoria dei grafi minori
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. Template:Chiarire 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 o di .
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 . Ciò implica una caratterizzazione dei grafi privi di minore , 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 ) della congettura di Hadwiger sul numero cromatico di un -grafo (di tipo ) 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[2] in modo analogo a quello in cui teorema di Wagner caratterizza i grafi planari.
La congettura fu resa pubblica molto tempo dopo[3], finché i matematici Neil Robertson e Paul Seymour riuscirono a dimostrarla nel 2004 con quello che fu chiamato il Teorema di Robertson-Seymour.[4]
Premi e riconoscimenti
- 1990: festschrift sulla teoria dei grafi[5];
- 2000: festkolloquium postumo all'Università di Colonia.
Opere selezionate
Note
- ↑ Template:Cita web
- ↑ Al riguardo, si può consultare la voce Forbidden graph characterization presente nella Wikipedia in inglese.
- ↑ Template:Cita pubblicazione
- ↑ Template:Cita pubblicazione.
- ↑ Template:Cita pubblicazione
Bibliografia
- Template:Cita pubblicazione (doi: 10.1002/1097-0118(200010)35:2<128::AID-JGT6>3.0.CO;2-6)