Klaus Wagner (31 de marzo de 1910 - 6 de febrero de 2000) fue un matemático alemán conocido por sus contribuciones a la teoría de grafos .
Educación y carrera
Wagner estudió topología en la Universidad de Colonia bajo la supervisión de Karl Dörge que había sido alumno de Issai Schur . Wagner recibió su Ph.D. en 1937, con una disertación sobre el teorema de la curva de Jordan y el teorema de los cuatro colores , y él mismo enseñó en Colonia durante muchos años. [1] En 1970, se trasladó a la Universidad de Duisburg , donde permaneció hasta su jubilación en 1978.
Graficar menores
Wagner es conocido por sus contribuciones a la teoría de grafos y particularmente a la teoría de grafos menores , grafos que se pueden formar a partir de un gráfico más grande al contraer y eliminar bordes.
El teorema de Wagner caracteriza a los grafos planares exactamente como aquellos grafos que no tienen como menor ni un grafo completo K 5 en cinco vértices ni un grafo bipartito completo K 3,3 con tres vértices a cada lado de su bipartición. Es decir, estas dos gráficas son las únicas gráficas no planas menores-mínimas. Está estrechamente relacionado con el teorema de Kuratowski , pero debe distinguirse del mismo, que establece que las gráficas planas son exactamente aquellas gráficas que no contienen como subgrafo una subdivisión de K 5 o K 3,3 .
Otro resultado de este, también conocido como teorema de Wagner, es que una gráfica de cuatro conexiones es plana si y solo si no tiene K 5 menor. Esto implica una caracterización de los gráficos sin K 5 menor como construidos a partir de gráficos planos y gráficos de Wagner (una escalera de Möbius de ocho vértices ) mediante sumas de clique , operaciones que unen subgráficos en cliques de hasta tres vértices y luego posiblemente eliminan bordes de esas camarillas. Esta caracterización fue utilizada por Wagner para demostrar que el caso k = 5 de la conjetura de Hadwiger sobre el número cromático de K k -gráficos libres de menores es equivalente al teorema de los cuatro colores . Las caracterizaciones análogas de otras familias de gráficos en términos de los sumandos de sus descomposiciones de suma de clique se han convertido desde entonces en estándar en la teoría de grafos menores.
Wagner conjeturó en la década de 1930 (aunque esta conjetura no se publicó hasta más tarde) [2] que en cualquier conjunto infinito de gráficos, un gráfico es isomorfo a un menor de otro. La verdad de esta conjetura implica que cualquier familia de gráficos cerrados bajo la operación de tomar menores (como son los gráficos planos) puede caracterizarse automáticamente por un número finito de menores prohibidos de manera análoga al teorema de Wagner que caracteriza los gráficos planos. Neil Robertson y Paul Seymour finalmente publicaron una prueba de la conjetura de Wagner en 2004 y ahora se conoce como el teorema de Robertson-Seymour . [3]
Reconocimiento
Wagner fue honrado en 1990 por un festival sobre teoría de grafos, [4] y en junio de 2000, luego de la muerte de Wagner, la Universidad de Colonia organizó un Festkolloquium en su memoria. [5]
Publicaciones Seleccionadas
- Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe" , Mathematische Annalen , 114 : 570–590, doi : 10.1007 / BF01594196[ enlace muerto permanente ] .
Referencias
- ^ Klaus Wagner en el Proyecto de genealogía matemática
- ^ Casselman, Bill, Variations on Graph Minor , American Mathematical Society.
- ^ Robertson, Neil ; Seymour, Paul (2004), "Graph Minors XX: Wagner's Conjecture", Journal of Combinatorial Theory, Serie B , 92 (2): 325–357, doi : 10.1016 / j.jctb.2004.08.001.
- ^ Bodendieck, Rainer, ed. (1990), Métodos contemporáneos en teoría de grafos: En honor al Prof.Dr. Klaus Wagner , Mannheim: Bibliographisches Institut, Wissenschaftsverlag, ISBN 978-3-411-14301-6.
- ↑ Festkolloquium in memoriam Klaus Wagner