Сильная теорема о совершенном графе - Strong perfect graph theorem

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

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

Заявление

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

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

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

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

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

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

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

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

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

А перекос раздела является разбиением вершин графа на два подмножества, одно из которых индуцирует несвязный подграф, а другое - несвязное дополнение; Chvátal (1985) предположил, что никакой минимальный контрпример к сильной гипотезе о совершенном графе не может иметь косого разбиения. Чудновский и др. ввел некоторые технические ограничения на косые перегородки и смогли показать, что гипотеза Хватала верна для результирующих «сбалансированных косых перегородок». Полная гипотеза является следствием сильной теоремы о совершенном графе.[8]

Однородная пара связана с модульная декомпозиция графа. Это разбиение графа на три подмножества V1, V2, и V3 такой, что V1 и V2 вместе содержат не менее трех вершин, V3 содержит не менее двух вершин, и для каждой вершины v в V3 и каждый я в {1,2} либо v смежна со всеми вершинами из Vя или никому из них. Минимально несовершенный граф не может иметь однородную пару.[9] После доказательства сильной гипотезы о совершенном графе Чудновский (2006) упростил его, показав, что однородные пары могут быть исключены из множества разложений, используемых в доказательстве.

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

Примечания

  1. ^ Маккензи (2002); Cornuéjols (2002).
  2. ^ Маккензи (2002).
  3. ^ "Премии Фулкерсона 2009" (PDF), Уведомления Американского математического общества: 1475–1476, декабрь 2011 г..
  4. ^ Cornuéjols (2002), Гипотеза 5.1.
  5. ^ Рид (1986); Хугарди (1991); Русу (1997); Руссель, Русу и Тюилье (2009), раздел 4.6 «Первые домыслы».
  6. ^ Руссель, Русу и Тюилье (2009), Определение 4.39.
  7. ^ Cornuéjols & Cunningham (1985); Cornuéjols (2002), Теорема 3.2 и следствие 3.3.
  8. ^ Сеймур (2006); Руссель, Русу и Тюилье (2009), раздел 4.7 «Косая перегородка»; Cornuéjols (2002), Теоремы 4.1 и 4.2.
  9. ^ Chvátal & Sbihi (1987); Cornuéjols (2002), Теорема 4.10.
  10. ^ Cornuéjols (2002), Теоремы 5.4, 5.5 и 5.6; Руссель, Русу и Тюилье (2009), Теорема 4.42.

Рекомендации

внешняя ссылка