Клаус Вагнер (31 марта 1910 — 6 февраля 2000) — немецкий математик , известный своим вкладом в теорию графов .
Вагнер изучал топологию в Кельнском университете под руководством Карла Дёрге который был учеником Иссаи Шура . Вагнер получил докторскую степень в 1937 году, защитив диссертацию по теореме о жордановой кривой и теореме о четырёх красках , и много лет сам преподавал в Кельне. [1] В 1970 году он перешёл в Дуйсбургский университет , где и оставался до выхода на пенсию в 1978 году.
Вагнер известен своим вкладом в теорию графов и, в частности, в теорию миноров графов — графов, которые можно образовать из большего графа путем сжатия и удаления ребер.
Теорема Вагнера характеризует планарные графы как именно те графы, которые не содержат в качестве минора ни полный граф K 5 на пяти вершинах, ни полный двудольный граф K 3,3 с тремя вершинами с каждой стороны его двудольного графа. То есть, эти два графа являются единственными минорно-минимальными непланарными графами. Она тесно связана с теоремой Куратовского , но ее следует отличать от нее, которая утверждает, что планарные графы — это именно те графы, которые не содержат в качестве подграфа подразделение K 5 или K 3,3 .
Другой его результат, также известный как теорема Вагнера, заключается в том, что четырехсвязный граф является планарным тогда и только тогда, когда он не имеет K 5 -минора. Это подразумевает характеристику графов без K 5 -минора как построенных из планарных графов и графа Вагнера (восьмивершинной лестницы Мёбиуса ) с помощью кликовых сумм , операций, которые склеивают подграфы в кликах до трех вершин, а затем, возможно, удаляют ребра из этих клик. Эта характеристика была использована Вагнером, чтобы показать, что случай k = 5 гипотезы Хадвигера о хроматическом числе графов без K k -миноров эквивалентен теореме о четырех цветах . Аналогичные характеристики других семейств графов в терминах слагаемых их кликовых суммовых разложений с тех пор стали стандартными в теории графовых миноров.
Вагнер предположил в 1930-х годах (хотя эта гипотеза была опубликована лишь позднее) [2] , что в любом бесконечном множестве графов один граф изоморфен минору другого. Истинность этой гипотезы подразумевает, что любое семейство графов, замкнутое относительно операции взятия миноров (каковыми являются планарные графы), может быть автоматически охарактеризовано конечным числом запрещенных миноров аналогично теореме Вагнера, характеризующей планарные графы. Нил Робертсон и Пол Сеймур наконец опубликовали доказательство гипотезы Вагнера в 2004 году, и теперь оно известно как теорема Робертсона–Сеймура . [3]
В 1990 году Вагнеру была посвящена юбилейная книга по теории графов [4] , а в июне 2000 года, после смерти Вагнера, Кельнский университет организовал юбилейный коллоквиум в его память [5] .