Введение

В теории графов теорема о сильной совершенности графов представляет собой запрещенную графовую характеристику совершенных графов, определяющую их как графы, не содержащие ни нечетных циклов нечётной длины (индуцированных циклов длиной не менее 5), ни нечетных антициклов (дополнений к нечетным циклам). Предположение об этой теореме выдвинул Клод Берж в 1961 году. Доказательство, предложенное Марией Чудновской, Нилом Робертсоном, Полом Сеймуром и Робином Томасом, было объявлено в 2002 году и опубликовано ими в 2006 году. За доказательство теоремы о сильной совершенности графов авторы получили премию в размере 10 000 долларов, предложенную Жераром Корнуэхольсом из Университета Карнеги — Меллона, и премию Фулкерсона 2009 года.

Заявление

Идеальный граф — это граф, в котором для каждого индуцированного подграфа размер максимальной клики равен минимальному числу цветов в раскраске графа; идеальные графы включают в себя многие известные классы графов, такие как двудольные графы, хордальные графы и графы сопоставимости. В своих работах 1961 и 1963 годов, впервые определяя этот класс графов, Клод Берж заметил, что идеальный граф не может содержать нечётный цикл (hole) — индуцированный подграф в виде цикла нечётной длины, состоящего из пяти или более вершин, поскольку нечётные циклы имеют число клики, равное двум, а хроматическое число — трём. Аналогично, он заметил, что идеальные графы не могут содержать нечётные антициклы (antihole) — индуцированные подграфы, дополняющие нечётные циклы: нечётный антицикл с 2k + 1 вершинами имеет число клики k и хроматическое число k + 1, что также невозможно для идеальных графов. Графы, не содержащие ни нечётных циклов, ни нечётных антициклов, стали известны как графы Бержа. Берж предположил, что каждый граф Бержа является идеальным, или, что эквивалентно, что идеальные графы и графы Бержа определяют один и тот же класс графов. Это предположение стало известно как гипотеза о сильной идеальности графов, пока оно не было доказано в 2002 году, после чего его переименовали в теорему о сильной идеальности графов.

Отношение к теореме слабого совершенного графа

Еще одна гипотеза Берге, доказанная в 1972 году Ласло Ловасом, утверждает, что дополнение любого совершенного графа также является совершенным. Это стало известно как теорема о совершенных графах, или (для отличия от сильной теоремы о совершенных графах) теорема о слабо совершенных графах. Поскольку запрещенная характеристика графа Берге самодополняема, теорема о слабо совершенных графах непосредственно следует из сильной теоремы о совершенных графах.

Доказательство идей

Доказательство теоремы о сильном совершенстве графов, выполненное Чудновским и др., следует плану, предложенному в 2001 году Конфорти, Корнуэжольсом, Робертсоном, Сеймуром и Томасом, согласно которому каждый граф Берге либо принадлежит к одному из пяти типов основных строительных блоков (специальные классы совершенных графов), либо имеет один из четырех различных типов структурного разложения на более простые графы. Минимально несовершенный граф Берге не может иметь ни одного из этих разложений, что означает, что не может существовать контрпримера к теореме. Эта идея основывалась на предыдущих предполагаемых структурных разложениях аналогичного типа, которые могли бы подразумевать гипотезу о сильном совершенстве графов, но оказались неверными. Пять основных классов совершенных графов, составляющих базовый случай этого структурного разложения, — это двудольные графы, линейные графы двудольных графов, дополнения двудольных графов, дополнения линейных графов двудольных графов и двойные разделенные графы. Очевидно, что двудольные графы совершенны: в любом нетривиальном индуцированном подграфе число клики и хроматическое число равны двум, и, следовательно, совпадают. Совершенство дополнений двудольных графов и дополнений линейных графов двудольных графов эквивалентно теореме Кёнига, связывающей размеры максимальных паросочетаний, максимальных независимых множеств и минимальных вершинных покрытий в двудольных графах. Совершенство линейных графов двудольных графов можно сформулировать эквивалентно тому факту, что двудольные графы имеют хроматический индекс, равный их максимальной степени. Таким образом, все четыре этих основных класса совершенны. Двойные разделенные графы являются разновидностью разделенных графов, которые также можно показать совершенными. Четыре типа разложений, рассматриваемых в этом доказательстве, — это 2-соединения, дополнения 2-соединений, сбалансированные косые разбиения и однородные пары. 2-соединение — это разбиение множества вершин графа на два подмножества, такое что ребра, соединяющие эти два подмножества, образуют два непересекающихся полных двудольных графа. Если граф имеет 2-соединение, его можно разложить на индуцированные подграфы, называемые «блоками», заменив одно из двух подмножеств вершин на кратчайший путь внутри этого подмножества, соединяющий один из двух полных двудольных графов с другим; если такого пути не существует, блок формируется путем замены одного из двух подмножеств вершин двумя вершинами, по одной для каждого полного двудольного подграфа. 2-соединение является совершенным тогда и только тогда, когда оба его блока совершенны. Следовательно, если минимально несовершенный граф имеет 2-соединение, он должен быть равен одному из своих блоков, что означает, что это должен быть нечетный цикл, а не граф Берге. По той же причине минимально несовершенный граф, чей комплемент имеет 2-соединение, не может быть графом Берге. Косое разбиение — это разбиение множества вершин графа на два подмножества, одно из которых индуцирует несвязный подграф, а другое имеет несвязное дополнение. Предполагалось, что ни один минимальный контрпример к гипотезе о сильном совершенстве графов не может иметь косого разбиения. Чудновский и др. ввели некоторые технические ограничения на косые разбиения и смогли показать, что предположение Шватала верно для полученных «сбалансированных косых разбиений». Полная гипотеза является следствием теоремы о сильном совершенстве графов. Однородная пара связана с модульным разложением графа. Это разбиение графа на три подмножества V1, V2 и V3, такие что V1 и V2 вместе содержат по крайней мере три вершины, V3 содержит по крайней мере две вершины, и для каждой вершины v в V3 и каждого i в {1, 2} либо v смежна со всеми вершинами в Vi, либо ни с одной из них. Минимально несовершенный граф не может иметь однородную пару. После доказательства теоремы о сильном совершенстве графов ее упростили, показав, что однородные пары можно исключить из набора разложений, используемых в доказательстве. Доказательство того, что каждый граф Берге принадлежит к одному из пяти основных классов или имеет один из четырех типов разложения, следует анализу случаев в зависимости от того, существуют ли в графе определенные конфигурации: «растяжка» — подграф, который можно разложить на три индуцированных пути с соблюдением определенных дополнительных ограничений, дополнение к растяжке и «правильное колесо» — конфигурация, связанная с графом-колесом, состоящая из индуцированного цикла вместе с центральной вершиной, смежной по крайней мере с тремя вершинами цикла и удовлетворяющей нескольким дополнительным ограничениям. Для каждого возможного выбора наличия растяжки или ее дополнения или правильного колеса в данном графе Берге можно показать, что граф принадлежит к одному из основных классов или подлежит разложению. Этот анализ случаев завершает доказательство.