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 .
Wagner estudió topología en la Universidad de Colonia bajo la supervisión de Karl Dörge quien había sido alumno de Issai Schur . Wagner recibió su doctorado en 1937, con una disertación sobre el teorema de la curva de Jordan y el teorema de los cuatro colores , y 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.
Wagner es conocido por sus contribuciones a la teoría de grafos y particularmente a la teoría de grafos menores , grafos que pueden formarse a partir de un grafo más grande contrayendo y eliminando aristas.
El teorema de Wagner caracteriza a los grafos planares como exactamente aquellos grafos que no tienen como menor ni un grafo completo K 5 en cinco vértices ni un grafo completo bipartito K 3,3 con tres vértices a cada lado de su bipartición. Es decir, estos dos grafos son los únicos grafos no planares menores-minimales. Está estrechamente relacionado con el teorema de Kuratowski , pero debe distinguirse de él , que establece que los grafos planares son exactamente aquellos grafos que no contienen como subgrafo una subdivisión de K 5 o K 3,3 .
Otro resultado suyo, también conocido como teorema de Wagner, es que un grafo cuatro-conexo es plano si y solo si no tiene ningún menor K 5. Esto implica una caracterización de los grafos sin ningún menor K 5 como construidos a partir de grafos planos y grafo de Wagner (una escalera de Möbius de ocho vértices ) por sumas de clique , operaciones que pegan subgrafos en cliques de hasta tres vértices y luego posiblemente eliminan aristas de esos cliques. Esta caracterización fue utilizada por Wagner para mostrar que el caso k = 5 de la conjetura de Hadwiger sobre el número cromático de K grafos libres de k -menores es equivalente al teorema de los cuatro colores . Caracterizaciones análogas de otras familias de grafos en términos de los sumandos de sus descomposiciones de suma de clique se han vuelto estándar desde entonces en la teoría de grafos menores.
En la década de 1930, Wagner conjeturó (aunque esta conjetura no se publicó hasta más tarde) [2] que en cualquier conjunto infinito de grafos, un grafo es isomorfo a un menor de otro. La verdad de esta conjetura implica que cualquier familia de grafos cerrada bajo la operación de tomar menores (como lo son los grafos planares) puede ser caracterizada automáticamente por un número finito de menores prohibidos de manera análoga al teorema de Wagner que caracteriza a los grafos planares. Neil Robertson y Paul Seymour finalmente publicaron una prueba de la conjetura de Wagner en 2004 y ahora se la conoce como el teorema de Robertson-Seymour . [3]
Wagner fue homenajeado en 1990 con un festival sobre teoría de grafos, [4] y en junio de 2000, tras la muerte de Wagner, la Universidad de Colonia organizó un Festkolloquium en su memoria. [5]