Сильна теорема про досконалі графи

Сильна теорема про досконалі графи — це характеризація забороненими графами досконалих графів як точно тих графів, які не мають ні непарних дір (породжених циклів непарної довжини), ні непарних антидір (доповнень непарним дірам). Гіпотезу висловив Берж^[en] 1961 року. Доведення Марії Чудновської, Нейла Робертсона^[en], Пола Сеймура^[en] та Робіна Томаса^[en] заявлено 2002 року[1][2] та опубліковано 2006 року.

За доведення сильної теореми про досконалі графи автори отримали приз $10,000 від Джерарда Корніджолса з університету Карнегі-Меллон [1] та премію Фалкерсона 2009 [3] .

Твердження теореми

Досконалий граф — це граф, у якому для будь-якого породженого підграфа розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Досконалі графи включають добре відомі класи графів: двочасткові графи, хордальні графи та графи порівнянності. У працях 1961 і 1963 років, визначаючи вперше цей клас графів, Берж^[en] зауважив, що досконалі графи не можуть містити непарної діри, породженого підграфа у формі циклу непарної довжини п'ять або більше, оскільки непарні діри мають клікове число два, а хроматичне число три. Аналогічно, він зауважив, що досконалі графи не можуть містити непарних антидір, породжених підграфів, доповнень непарних дір — непарна антидіра з ${\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].

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

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

Доведення, що будь-який граф Бержа потрапляє в один із п'яти класів або має один з чотирьох типів декомпозиції, спирається на розбір окремих випадків, згідно з яким існує певна конфігурація у графі — розтяжка, підграф, який можна розкласти на три породжені шляхи згідно з певними додатковими обмеженнями, доповнення розтяжки та власне колесо, конфігурація, пов'язана з колесом, що складається з породженого циклу разом із центральною вершиною, суміжною щонайменше з трьома вершинами обода і задовольняє деяким додатковим обмеженням. Залежно від того, чи існує всередині заданого графа Бержа розтяжка, доповнення розтяжки або власне колесо, можна показати, що граф належить до одного з базових класів, або може бути підданий декомпозиції[20][21]. Цей аналіз випадків завершує доведення.

Примітки

1. Mackenzie, 2002.
2. Cornuéjols, 2002.
3. 2009 Fulkerson Prizes, 2011, с. 1475–1476.
4. Cornuéjols, 2002, с. Гіпотеза 5.1.
5. Reed, 1986.
6. Hougardy, 1991.
7. Rusu, 1997.
8. Roussel, Rusu, Thuillier, 2009, с. розділ 4.6 The first conjectures.
9. Kőnig, 1916.
10. Roussel, Rusu, Thuillier, 2009, с. Визначення 4.39.
11. Cornuéjols, Cunningham, 1985.
12. Cornuéjols, 2002, с. Теорема 3.2 і наслідок 3.3.
13. Chvátal, 1985.
14. Seymour, 2006.
15. Roussel, Rusu, Thuillier, 2009, с. розділ 4.7 The skew partition.
16. Cornuéjols, 2002, с. Теореми 4.1 і 4.2.
17. Chvátal, Sbihi, 1987.
18. Cornuéjols, 2002, с. Теорема 4.10.
19. Chudnovsky, 2006.
20. Cornuéjols, 2002, с. Теореми 5.4, 5.5, 5.6.
21. Roussel, Rusu, Thuillier, 2009, с. Теорема 4.42.

Література

• 2009 Fulkerson Prizes // Notices of the American Mathematical Society. — 2011. — Т. 57, № 11 (December). — С. 1475–1476. — ISSN 0002-9920.
• Claude Berge. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10. — С. 114..
• Claude Berge. Perfect graphs // Six Papers on Graph Theory. — Calcutta : Indian Statistical Institute, 1963. — С. 1–21.
• Maria Chudnovsky. Berge trigraphs // Journal of Graph Theory. — 2006. — Т. 53, вип. 1. — С. 1–55. — DOI:10.1002/jgt.20165.
• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51–229. — arXiv:math/0212070. — DOI:10.4007/annals.2006.164.51.
• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Progress on perfect graphs // Mathematical Programming. — 2003. — Т. 97, вип. 1–2. — С. 405–422. — (Series B.). — DOI:10.1007/s10107-003-0449-8.
• Václav Chvátal. Star-cutsets and perfect graphs // Journal of Combinatorial Theory. — 1985. — Т. 39, вип. 3. — С. 189–199. — (Series B). — DOI:10.1016/0095-8956(85)90049-8..
• Václav Chvátal, Najiba Sbihi. Bull-free Berge graphs are perfect // Graphs and Combinatorics. — 1987. — Т. 3, вип. 2. — С. 127–139. — DOI:10.1007/BF01788536..
• Gérard Cornuéjols. The strong perfect graph conjecture // Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002). — Beijing : Higher Ed. Press, 2002. — С. 547–559. Архівна копія на сайті Wayback Machine.
• Gérard Cornuéjols, Cunningham W. H. Compositions for perfect graphs // Discrete Mathematics. — 1985. — Т. 55, вип. 3. — С. 245–254. — DOI:10.1016/S0012-365X(85)80001-7.
• Hougardy S. Counterexamples to three conjectures concerning perfect graphs. — Grenoble, France : Laboratoire Artemis-IMAG, Universitá Joseph Fourier, 1991. — (Technical Report RR870-M). Як процитовано в статті Roussel, Rusu, Thuillier, (2009).
• Dénes Kőnig. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. — 1916. — Т. 34. — С. 104–119.
• László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972a. — Т. 2, вип. 3. — С. 253–267. — DOI:10.1016/0012-365X(72)90006-4.
• László Lovász. A characterization of perfect graphs // Journal of Combinatorial Theory. — 1972b. — Т. 13, вип. 2. — С. 95–98. — (Series B). — DOI:10.1016/0095-8956(72)90045-7.
• Dana Mackenzie. Mathematics: Graph theory uncovers the roots of perfection // Science. — 2002. — Т. 297, вип. 5578 (July). — С. 38. — DOI:10.1126/science.297.5578.38. — PMID 12098683 .
• Bruce A. Reed. A semi-strong perfect graph theorem. — Montréal, Québec, Canada : Department of Computer Science, McGill University, 1986. — (Ph.D. thesis). Как процитировано в статье Roussel, Rusu, Thuillier, (2009).
• Roussel F., Rusu I., Thuillier H. The strong perfect graph conjecture: 40 years of attempts, and its resolution // Discrete Mathematics. — 2009. — Т. 309, вип. 20. — С. 6092–6113. — DOI:10.1016/j.disc.2009.05.024.
• Irena Rusu. Building counterexamples // Discrete Mathematics. — 1997. — Т. 171, вип. 1–3. — С. 213–227. — DOI:10.1016/S0012-365X(96)00081-7.
• Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — Вип. 109. — С. 69–83.

Посилання

• The Strong Perfect Graph Theorem, Václav Chvátal
• Weisstein, Eric W. Сильна теорема про досконалі графи(англ.) на сайті Wolfram MathWorld.