Сильная гипотеза о совершенных графах
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж[англ.] в 1961. Доказательство Марии Чудновской[англ.], Нейла Робертсона[англ.], Пола Сеймура и Робина Томаса было заявлено в 2002[1][2] и опубликовано ими в 2006.
За доказательство сильной теоремы о совершенных графах авторы получили приз в $10,000, выставленный Джерардом Корниджолс из университета Карнеги — Меллона[1] и премию Фалкерсона 2009 года[3].
Совершенный граф — это граф, в котором для любого порождённого подграфа размер наибольшей клики равен наименьшему числу цветов, необходимых для раскраски графа. Совершенные графы включают хорошо известные классы графов, такие как двудольные графы, хордальные графы и графы сравнимости. В работах 1961 и 1963 годов, определяя впервые эти классы графов, Берж[англ.] заметил, что совершенные графы не могут содержать нечётную дыру, порождённый подграф в форме цикл нечётной длины пять или более, поскольку нечётные дыры имеют кликовое число два, а хроматическое число три. Аналогично, он заметил, что совершенные графы не могут содержать нечётных антидыр, порождённых подграфов, дополнительных нечётным дырам — нечётная антидыра с вершинами имеет кликовое число k и хроматическое число , что снова невозможно для совершенных графов. Графы, не имеющие ни нечётных дыр, ни нечётных антидыр, стали известны как графы Бержа.
Берж высказал предположение, что любой граф Бержа совершенен, или, эквивалентно, что совершенные графы и графы Бержа определяют тот же самый класс графов. Это предположение было известно как сильная гипотеза о совершенных графах вплоть до её доказательства в 2002, когда она была переименована в сильную теорему о совершенных графах.
Другая гипотеза Бержа, доказанная в 1972 Ласло Ловасом, утверждает, что дополнение любого совершенного графа также совершенно. Теорема стала известна как теорема о совершенных графах или (чтобы отличать её от сильной гипотезы/теоремы о совершенных графах) слабой теоремой о совершенный графах. Поскольку характеризация запрещёнными графами Бержа самодвойственна, слабая теорема о совершенных графах следует немедленно из сильной теоремы о совершенных графах.