§ 61. Совершенные графы

Как отмечалось выше, хроматическое число и плот­ность любого графа удовлетворяют очевидному неравен­ству χ(G)≥φ(G). При этом, как свидетельствует теоре­ма 54.5, разность χ(G) - φ(G) может быть как угодно велика. В этом параграфе изучаются графы, обладающие тем свойством, что хроматическое число и плотность не только самого графа, но и каждого его порожденного подграфа, равны.

Граф называется совершенным, если

χ(H )= φ(H) (1)

для любого его порожденного подграфа H.

Из этого определения непосредственно вытекает, что всякий порожденный подграф любого совершенного гра­фа является совершенным.

Очевидно, что все полные и пустые графы совершенны. Примером совершенного графа может служить также каждый двудольный граф поскольку для любого его под­графа H либо χ(H )=φ(H)=2 (если H непустой), либо χ(H )=φ(H)=1 (при пустом H).

Совершенные графы введены К. Бержем в I960 году. Интерес к этим графам связан прежде всего с двумя обстоятельствами. Во-первых, многие трудно разрешимые в общем случае задачи теории графов успешно решают­ся для совершенных графов. Во-вторых, ряд широко известных классов графов содержится в классе совершенных. Таковы, например, все двудольные, пороговые, расщепляемые и триангулированные (см. § 62) графы. Исследования, посвященные совершенным графам и, в частности, связанной с ними гипотезе Бержа, речь о которой пойдет ниже, во многом определяют лицо современной теории графов.

Теорема 61.1. Граф, дополнительный к совершенному графу, также является совершенным.

Эту теорему в виде гипотезы сформулировал К. Берж 1961 г. Позже ее независимо доказали Д. Р. Фалкерон (1971 г.) и Л. Ловас (1972 г.). Ниже приводится доказательство Л. Ловаса.

Лемма 61.2. Следующие два утверждения равносильны:

1. граф G является совершенным;

2. влюбом непустом порожденном подграфеG' графа G есть такое независимое множество вершин А, что

Пусть G — совершенный граф, G' — его непустой порожденный подграф. Тогда χ(G') = φ(G'). Следовательно, существует правильная φ(G')-раскраска графа G'. если А — какой-либо цветной класс при этой раскраске, то множество А независимо и χ(G'— A) ≤φ(G')— 1. Из последнего неравенства вытекает (2), поскольку φ(H) ≤ χ(H) для любого графа H.

Пусть теперь для некоторого графаG верно утверж­дение 2). Нужно доказать, что для любого порожденно­го подграфа G' графа G выполняется неравенство

Из неравенства (3) следует равенство плотности и хро­матического числа, ибо противоположное неравенство всегда верно. Воспользуемся индукцией по \G’\. Если G' — пустой граф, то (3) тривиально. Пусть G' непуст, \G'\ =k > 1 и для каждого порожденного подграфа мень­шего чем k порядка верно неравенство, аналогичное не­равенству (3). Для независимого множества А вершин графа G', удовлетворяющего неравенству (2), имеем по индуктивному предположению:

Но так как множествоА независимо, то

и равенство (3) доказано.

Пусть G и H — произвольные графы. Будем считать их множества вершин не пересекающимися и следующим образом определим новый граф F. Отметим произвольную вершину v графа G и положим VF = (VG U VH)\v. Вер­шины а и b графа F будем считать смежными, если вы­полняется одно из следующих трех условий:

1. ab € EG,

2. аb€ЕН,

3. a € VG, b €VH, av €EG или b € VG, a €VH, bv € EG.

Скажем, что граф F получается из графа G в резуль­тате замены вершины v графом Я.

Лемма 61.3. Граф, полученный из совершенного графа в результате замены вершин совершенными гра­фами, также является совершенным.

Очевидно, что достаточно рассмотреть лишь одну замену вершины. Пусть G и H — совершенные графы, a F получается из G в результате замены вершины v гра­фом Я. Учитывая лемму 61.2, достаточно показать, что в любом порожденном подграфе F' графа F есть незави­симое множество вершин А, пересекающееся с каждой наибольшей кликой графа F'. Вначале пусть F' = F. За­фиксируем какую-либо правильную φ(G)-раскраску гра­фа G. Пусть В — цветной класс, содержащий вершину v. Выберем в графе Н такое независимое множество вершин С, что φ(H - С) < φ(С). Теперь покажем, что множество (BUC)\v = А удовлетворяет нужным условиям. В самом деле, В независимо в G, С независимо в Н. Если же b € B \ v, c € C, то вершины b и v не смежны в G, а потому b и с не смежны в F. Итак, А — независимое множество вершин графа F.

Остается показать, что А пересекается с каждой наи­большей кликой графа F. Пусть К — одна из таких клик, L = К ∩ VH. Если L ≠ 0, то L содержит какую-либо наибольшую клику D графа H, поскольку любая вершина рафа G — v либо смежна в F с каждой вершиной графа H, либо ни с одной из них. Так как D∩C ≠ 0, то К ∩ А ≠ 0. Если же L = 0, то K€VG\v, φ(F)=\K\ ≤ φ(G — v) ≤ φ(G). Но очевидно, что φ(G) ≤ φF). Следовательно, \K\ = φ(G), клика К пересекается с каждым цветным классом любой правильной φ(G)-раскраски графа G, К∩(B\v)≠0, значит, К ∩ А ≠ 0. Доказано, то в графе F есть независимое множество вершин, юторое пересекается с каждой наибольшей кликой того графа.

Теперь заметим, что аналогичное свойство имеет любой порожденный подграф F' графа F, поскольку F' либо получается из некоторого порожденного подграфа G' графа G в результате замены вершины v порожденным подграфом Н' графа Н, либо является порожденным подграфом графа G.

Лемма 61.4. В любом совершенном графе G есть лика, пересекающая каждое наибольшее независимое ножество вершин графа G.

Проведем доказательство от противного. Пусть G — тершенный граф, для каждой клики В которого суще-гвует такое наибольшее независимое множество вершин , что В∩А=¢. Пусть, далее, В₁, ..., В_г — список всех клик графа G, А_i — наибольшее независимое множество вершин, такое что А_i ∩ В_i≠ 0 (i=1,r). Для произвольной вершины v графа G обозначим через w(u) число всех ножеств А_i, содержащих эту вершину. Заменив в G каждую вершину v полным графом K_w(v), получим граф G', который по лемме 61.3 окажется совершенным. Оценим число φ(С). Очевидно, что всякая клика графа G' есть объединение клик графов, заменивших в G вершины какой-либо клики. Поэтому

Поскольку каждое из множеств А_i вносит единицу в те и только те из чисел w{v), для которых v € Aj, то

Но очевидно, что

Следовательно,

Далее,

(теорема 54.7). Построим последовательность, выписав поочередно все элементы множества А1, все элементы множества А2, ..., все элементы множества Аr .Пусть l — длина этой последовательности. Очевидно, что

С другой стороны, каждая вершина v графа G фигури­рует в этой последовательности ровно w(v) раз, поэтому

Наконец, очевидно, ao(G') = ao(G).

Неравенство (5) теперь принимает вид

Но φ(G') = χ(G'), что противоречит совокупности нера­венств (4) и (6). Полученное противоречие и доказыва­ет лемму.

Доказательство теоремы 61.1. Пусть G — совершенный граф, Н —_непустой порожденный подграф дополнительного графа G’. Тогда Н’ — порожденный под­граф графа G. Согласно лемме 61.4 в графе Н’ есть кли­ка В, пересекающаяся с каждым наибольшим независи­мым подмножеством вершин. В графе Н множество В не­зависимо и пересекается с каждой наибольшей кликой. Следовательно, в силу леммы 61.2 граф G’ является со­вершенным.

Напомним читателю, что c(G) означает число кликового покрытия графа G. Очевидно, что αо(G) = φ(G’), c(G) = χ(G), поэтому из теоремы 61.1 вытекает

Следствие 61.5. Граф является совершенным тог­да и только тогда, когда ао(Н) = с(Н) для любого его по­рожденного подграфа Н.

Приведем без доказательства теорему, характеризую­щую совершенные графы в терминах многогранников. С каждой бинарной матрицей А без нулевых столбцов можно связать два многогранника: многогранник Р(А) ={х: Ax ≤ 1, х ≥ 0}, введенный в § 28, и многогранник Р_с (А) — выпуклую оболочку множества целых точек мно­гогранника Р(А). Очевидно, что Р_С(А) € Р(А).

Теорема 61.6. (В. Хватал, 1975 г.). Пусть А — матрица клик графа G. Тогда для того, чтобы граф G был совершенным, необходимо и достаточно выполнение равенства Р_С(А) = Р(А).

Легко видеть, что условием, необходимым для того, чтобы граф был совершенным, является отсутствие в нем порожденных простых циклов нечетной длины l ≥ 5. В самом деле, если С — такой цикл, то φ(С) = 2 < χ(С) = 3. Из теоремы 61.1 вытекает, что таких циклов нe должен содержать и граф, дополнительный к совер­шенному. В 1962 году К. Берж высказал предположение, то эти два условия не только необходимы, но и достаточны для того, чтобы граф был совершенным.

Сильная гипотеза Берж а. Граф G является совершенным тогда и только тогда, когда ни он, ни его дополнение G не содержат порожденных подграфов вида G_2h+hk>2.

Эта гипотеза, не доказанная и не опровергнутая до зго времени, инициировала исследование совершенных эафов и привела ко многим интересным результатам.