Сильная гипотеза о совершенных графах

Совершенный граф — это граф, в котором для любого порождённого подграфа размер наибольшей клики равен наименьшему числу цветов, необходимых для раскраски графа. Совершенные графы включают хорошо известные классы графов, такие как двудольные графы, хордальные графы и графы сравнимости. В работах 1961 и 1963 годов, определяя впервые эти классы графов, Берж заметил, что совершенные графы не могут содержать нечётную дыру, порождённый подграф в форме цикл нечётной длины пять или более, поскольку нечётные дыры имеют кликовое число два, а хроматическое число три. Аналогично, он заметил, что совершенные графы не могут содержать нечётных антидыр, порождённых подграфов, дополнительных нечётным дырам — нечётная антидыра с ${\displaystyle 2k+1}$ вершинами имеет кликовое число k и хроматическое число ${\displaystyle k+1}$, что снова невозможно для совершенных графов. Графы, не имеющие ни нечётных дыр, ни нечётных антидыр, стали известны как графы Бержа.

Берж высказал предположение, что любой граф Бержа совершенен, или, эквивалентно, что совершенные графы и графы Бержа определяют тот же самый класс графов. Это предположение было известно как сильная гипотеза о совершенных графах вплоть до её доказательства в 2002, когда она была переименована в сильную теорему о совершенных графах.

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

Доказательство сильной теоремы о совершенных графах Чудновской с соавторами следует наброску, который предложили в 2001 году Конфорти, Корниджолс, Робертсон, Сеймур и Томас. Согласно этому наброску любой граф Бержа либо образует один из пяти типов базовых блоков (специальные классы совершенных графов), либо имеет одну из четырёх других типов структурных декомпозиций на более простые графы. Минимальный несовершенный граф Бержа не может иметь какую-либо из этих декомпозиций, откуда следует, что контрпример теореме не может существовать[4]. Эта идея была основана на гипотезе о структурной декомпозиции подобных типов, из которой следовала бы сильная гипотеза о совершенных графах, но гипотеза не оказалась справедливой[5][6][7][8].

Пять основных классов совершенных графов, образующих основные случаи этой структурной декомпозиции, это двудольные графы, рёберные графы двудольных графов, дополнения двудольных графов, дополнения рёберных графов двудольных графов и двойные расщепляемые графы. Легко видеть, что двудольные графы совершенны — в любом нетривиальном порождённом подграфе, как кликовое число, так и хроматическое число равны двум. Совершенство дополнений двудольных графов и дополнений рёберных графов двудольных графов эквивалентно теореме Кёнига относительно размеров наибольших паросочетаний, наибольших независимых множеств и наибольших вершинных покрытий в двудольных графах. Совершенство рёберных графов двудольных графов может быть сформулировано эквивалентно как факт, что двудольные графы имеют хроматический индекс, равный их наибольшей степени, что доказал Кёниг[9]. Таким образом, все четыре эти базовых класс совершенны. Двойные расщепляемые графы родственны расщепляемым графам в том, что также можно показать их совершенство[10].

Четыре типа декомпозиции, рассматриваемых в этом доказательстве, — это 2-соединения, дополнения 2-соединений, сбалансированные косые разбиения и однородные пары.

2-соединение — это разбиение вершин графа на два подмножества со свойством, что рёбра, стягивающие разрез между этими двумя подмножествами, образуют двухвершинные не пересекающиеся (по вершинам) полные двудольные графы. Когда граф имеет 2-соединение, его можно разложить на порождённые подграфы, называемые «блоками» путём замены одного из двух подмножеств вершин на кратчайший путь внутри этого подмножества, который соединяет один из двух полных двудольных графов с другим. Если такого пути не существует, блок образуется вместо этого путём замены одного из подмножеств вершин двумя вершинами, по одной для каждого полного двудольного подграфа. 2-соединение совершенно тогда и только тогда, когда оба его блока совершенны. Таким образом, если минимальный несовершенный граф имеет 2-соединение, он должен быть равен одному из его блоков, откуда следует, что он должен быть нечётным циклом и не быть графом Бержа. По той же причине минимальный несовершенный граф, дополнение которого имеет 2-соединение, не может быть графом Бержа[11][12].

Косое разбиение — это разбиение вершин графа на два подмножества, одно из которых пoрождает несвязный подграф, а другое имеет несвязное дополнение. Хватал[13] высказал гипотезу, что никакой минимальный контрпример сильной гипотезе о совершенных графах не может иметь косое разбиение. Чудновская и соавторы ввели некоторые технические ограничения на косые разбиения и смогли показать, что гипотеза Хватала верна для получающихся «сбалансированных косых разбиений». Полная гипотеза является следствием сильной теоремы о совершенных графах[14][15][16].

Однородные пары связаны с модульным разложением графа. Это разложение графа на три подмножества ${\displaystyle V_{1},V_{2},V_{3}}$, такие, что ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$ вместе содержат по меньшей мере три вершины, ${\displaystyle V_{3}}$ содержит по меньшей мере две вершины, а для каждой вершины v из ${\displaystyle V_{3}}$ и любого i из {1,2} либо v смежна всем вершинам в ${\displaystyle V_{i}}$, либо ни одной из них. Невозможно для минимального несовершенного графа иметь однородную пару[17][18]. После доказательства сильной гипотезы о совершенных графах Чудновская[19] упростила доказательство, показав, что однородные пары могут быть исключены из набора декомпозиций, используемых в доказательстве.

Доказательство, что любой граф Бержа попадает в один из пяти классов или имеет один из четырёх типов декомпозиции, следует разбору отдельных случаев, согласно которому существует определённая конфигурация в графе — «растяжка», подграф, который может быть разложен на три порождённые пути согласно определённым дополнительным ограничениям, дополнение растяжки и «собственное колесо», конфигурация, связанная с колесом, состоящим из порождённого цикла вместе центральной вершиной, смежной по меньшей мере с тремя вершинами обода и удовлетворяющей некоторые дополнительные ограничения. В зависимости от того, существует ли растяжка, дополнение к растяжке или собственное колесо внутри заданного графа Бержа, можно показать, что граф принадлежит одному из базовых классов, или может быть подвергнут декомпозиции[20][21]. Этот разбор случаев завершает доказательство.

• The Strong Perfect Graph Theorem, Václav Chvátal
• Weisstein, Eric W. Strong Perfect Graph Theorem (англ.) на сайте Wolfram MathWorld.