Сильная теорема об идеальном графе

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

Доказательство сильной теоремы о совершенном графе принесло ее авторам премию в размере 10 000 долларов, предложенную Жераром Корнюжолем из Университета Карнеги-Меллон. и премия Фулкерсона 2009 года .

Заявление

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

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

Связь с теоремой о слабом идеальном графе

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

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

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

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

В этом доказательстве рассматриваются четыре типа разложений: 2-соединения, дополнения 2-соединений, сбалансированные косые разбиения и однородные пары.

2-соединение — это разбиение вершин графа на два подмножества, причем ребра, охватывающие разрез между этими двумя подмножествами, образуют два непересекающихся по вершинам полных двудольных графа . Когда граф имеет 2-соединение, его можно разложить на индуцированные подграфы, называемые «блоками», путем замены одного из двух подмножеств вершин кратчайшим путем внутри этого подмножества, который соединяет один из двух полных двудольных графов с другим; когда такого пути не существует, вместо этого блок формируется путем замены одного из двух подмножеств вершин двумя вершинами, по одной для каждого полного двудольного подграфа. 2-соединение является совершенным тогда и только тогда, когда оба его блока идеальны. Следовательно, если минимально несовершенный граф имеет 2-соединение, оно должно равняться одному из своих блоков, из чего следует, что это должен быть нечетный цикл, а не цикл Бержа. По той же причине минимально несовершенный граф, дополнение которого имеет 2-соединение, не может быть Берджем.

Косое разбиение — это разбиение вершин графа на два подмножества, одно из которых порождает несвязный подграф, а другое имеет несвязное дополнение; Хватал (1985) предположил, что ни один минимальный контрпример к гипотезе сильного идеального графа не может иметь косого разбиения. Чудновский и др. ввели некоторые технические ограничения на косые разделы и смогли показать, что гипотеза Хватала верна для полученных в результате «сбалансированных косых разделов». Полная гипотеза является следствием сильной теоремы о совершенном графе.

Однородная пара связана с модульным разложением графа. Это разбиение графа на три подмножества V ₁ , V ₂ и V ₃ такое, что V ₁ и V ₂ вместе содержат не менее трех вершин, V ₃ содержит не менее двух вершин и для каждой вершины v в V ₃ и каждый i в {1,2} либо v соседен со всеми вершинами в V _i, либо ни с одной из них. Минимально несовершенный граф не может иметь однородную пару. После доказательства гипотезы сильного идеального графа Чудновский (2006) упростил ее, показав, что однородные пары можно исключить из набора разложений, использованных в доказательстве.

Доказательство того, что каждый граф Берге попадает в один из пяти основных классов или имеет один из четырех типов декомпозиции, следует за анализом случаев в зависимости от того, существуют ли внутри графа определенные конфигурации: «расширитель», подграф, который можно разложить на три индуцированных пути с некоторыми дополнительными ограничениями, дополнением подрамника и «собственным колесом», конфигурацией, связанной с графом колеса , состоящей из индуцированного цикла вместе с вершиной-ступицей, смежной как минимум с тремя вершинами цикла и подчиняющейся нескольким дополнительные ограничения. Для каждого возможного выбора того, существует ли подрамник, его дополнение или собственное колесо в данном графе Бержа, можно показать, что граф принадлежит одному из основных классов или является разложимым. Анализ данного случая завершает доказательство.

Ссылки

• Берге, Клод (1961), «Раскраска графов, все или нечетные окружности которых жесткие», Wiss. З. Мартина Лютера Univ. Галле-Виттенберг Математика-Природа. Строка , 10 :114 .
• Берге, Клод (1963), «Идеальные графики», Шесть статей по теории графов , Калькутта: Индийский статистический институт, стр. 1–21 .
• Чудновский, Мария (2006), «Триграфы Берге», Журнал теории графов , 53 (1): 1–55, doi : 10.1002/jgt.20165 , MR   2245543 .
• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , MR   2233847 .
• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2003), «Прогресс в создании идеальных графов», Математическое программирование , Серия B., 97 (1–2): 405–422, CiteSeerX   10.1.1.137.3013 , doi : 10.1007/s10107-003-0449-8 , МР   2004404 .
• Хватал, Вацлав (1985), «Звездные разрезы и совершенные графы», Журнал комбинаторной теории , серия B, 39 (3): 189–199, doi : 10.1016/0095-8956(85)90049-8 , MR   0815391 .
• Хватал, Вацлав ; Сбихи, Наджиба (1987), «Бычьи графы Бержа идеальны», Graphs and Combinatorics , 3 (2): 127–139, doi : 10.1007/BF01788536 , MR   0932129 .
• Корнюжоль, Жерар (2002), «Гипотеза о сильном совершенном графе», Труды Международного конгресса математиков, Vol. III (Пекин, 2002) (PDF) , Пекин: Высшее изд. Пресс, стр. 547–559, МР   1957560 .
• Корнюжоль, Г. ; Каннингем, WH (1985), «Композиции для совершенных графов», Discrete Mathematics , 55 (3): 245–254, doi : 10.1016/S0012-365X(85)80001-7 , MR   0802663 .
• Хугарди, С. (1991), Контрпримеры к трем гипотезам, касающимся совершенных графов , Технический отчет RR870-M, Гренобль, Франция: Laboratoire Artemis-IMAG, Universitá Joseph Fourier . Цитируется Русселем , Русу и Тюилье (2009) .
• Кениг, Денес (1916), «Графы и их применение к теории определителей и множеств», Mathematical and Natural Science Bulletin , 34 : 104–119 .
• Ловаш, Ласло (1972a), «Нормальные гиперграфы и гипотеза идеального графа», Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 .
• Ловас, Ласло (1972b), «Характеристика совершенных графов», Журнал комбинаторной теории , серия B, 13 (2): 95–98, doi : 10.1016/0095-8956(72)90045-7 .
• Маккензи, Дана (5 июля 2002 г.), «Математика: теория графов раскрывает корни совершенства», Science , 297 (5578): 38, doi : 10.1126/science.297.5578.38 , PMID   12098683 .
• Рид, Б.А. (1986), Полустрогая теорема об идеальном графике , доктор философии. диссертация, Монреаль, Квебек, Канада: факультет компьютерных наук, Университет Макгилла . Цитируется Русселем , Русу и Тюилье (2009) .
• Руссель, Ф.; Русу, И.; Тюилье, Х. (2009), «Гипотеза о сильном совершенном графе: 40 лет попыток и ее решение», Discrete Mathematics , 309 (20): 6092–6113, doi : 10.1016/j.disc.2009.05.024 , MR   2552645 .
• Русу, Ирена (1997), «Построение контрпримеров», Дискретная математика , 171 (1–3): 213–227, doi : 10.1016/S0012-365X(96)00081-7 , MR   1454452 .
• Сеймур, Пол (2006), «Как было найдено доказательство сильной гипотезы о совершенном графе» (PDF) , Gazette des Mathématiciens (109): 69–83, MR   2245898 .

Внешние ссылки

• Теорема о сильном совершенном графе , Вацлав Хватал
• Вайсштейн, Эрик В. «Сильная теорема о совершенном графе» . Математический мир .