Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Сильна теорема про досконалі графи це характеризація забороненими графами досконалих графів як точно тих графів які не м

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

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

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

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

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

Досконалий граф — це граф, у якому для будь-якого породженого підграфа розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Досконалі графи включають добре відомі класи графів: двочасткові графи, хордальні графи та графи порівнянності. У працях 1961 і 1963 років, визначаючи вперше цей клас графів, [en] зауважив, що досконалі графи не можуть містити непарної діри, породженого підграфа у формі циклу непарної довжини п'ять або більше, оскільки непарні діри мають клікове число два, а хроматичне число три. Аналогічно, він зауважив, що досконалі графи не можуть містити непарних антидір, породжених підграфів, доповнень непарних дір — непарна антидіра з image вершинами має клікове число k та хроматичне число image що знову ж неможливо для досконалих графів. Графи, які не мають ні непарних дір, ні непарних антидир, стали відомі як графи Бержа.

Берж висловив припущення, що будь-який граф Бержа досконалий, або, еквівалентно, що досконалі графи та графи Бержа визначають той самий клас графів. Це припущення було відомим як сильна гіпотеза про досконалі графи аж до її доведення 2002 року, коли її перейменовано на сильну теорему про досконалі графи.

Зв'язок зі слабкою теоремою про досконалі графи

Інша гіпотеза Бержа, яку довів 1972 року Ласло Ловас, стверджує, що доповнення будь-якого досконалого графа також досконале. Теорема стала відомою як теорема про досконалі графи або (щоб відрізняти її від сильної гіпотези/теореми про досконалі графи) слабка теорема про досконалі графи. Оскільки характеризування забороненими графами Бержа самодвоїсте, слабка теорема про досконалі графи випливає негайно із сильної теореми про досконалі графи.

Ідеї доведення

Доведення сильної теореми про досконалі графи Чудновської зі співавторами спирається начерк, який запропонували 2001 року Конфорті, Корніджолс, Робертсон, Сеймур і Томас. За цим начерком будь-який граф Бержа або утворює один із п'яти типів базових блоків (спеціальні класи досконалих графів), або має одну з чотирьох інших типів структурних декомпозицій на простіші графи. Мінімальний недосконалий граф Бержа не може мати жодної з цих декомпозицій, звідки випливає, що контрприкладу теоремі не може існувати. Ця ідея була ґрунтується на гіпотезі про структурну декомпозицію подібних типів, з якої випливала б сильна гіпотеза про досконалі графи, але гіпотеза не виявилася справедливою.

П'ять основних класів досконалих графів, що утворюють основні випадки цієї структурної декомпозиції, це двочасткові графи, реберні графи двочасткових графів, доповнення двочасткових графів, доповнення реберних графів двочасткових графів і подвійні розщеплювані графи. Легко бачити, що двочасткові графи досконалі — у будь-якому нетривіальному породженому підграфі, як клікове число, і хроматичне число рівні двом. Досконалість доповнень двочасткових графів та доповнень реберних графів двочасткових графів еквівалентна теоремі Кеніга щодо розмірів найбільших парувань, найбільших незалежних множин та найбільших вершинних покриттів у двочасткових графах. Досконалість реберних графів двочасткових графів можна сформулювати еквівалентно як факт, що двочасткові графи мають хроматичний індекс, рівний їх найбільшому степеню, що довів Кеніг. Таким чином, усі ці чотири базові класи досконалі. Подвійні розщеплювані графи споріднені розщеплюваним графам у тому, що також можна показати їх досконалість.

Чотири типи декомпозиції, розглянутих у цьому доведенні, — це 2-з'єднання, доповнення 2-з'єднань, збалансовані косі розбиття та однорідні пари.

2-з'єднання — це розбиття вершин графа на дві підмножини зі властивістю, що ребра, які стягують розріз між цими двома підмножинами, утворюють двовершинні повні двочасткові графи, що не перетинаються (вершинами). Коли граф має 2-з'єднання, його можна розкласти на породжені підграфи, звані «блоками», заміною однієї з двох підмножин вершин найкоротшим шляхом усередині цієї підмножини, який з'єднує один з двох повних двочасткових графів з іншим. Якщо такого шляху не існує, блок утворюється натомість заміною однієї з підмножин вершин двома вершинами, по одній для кожного повного двочасткового підграфа. 2-з'єднання досконале тоді й лише тоді, коли обидва його блоки досконалі. Таким чином, якщо мінімальний недосконалий граф має 2-з'єднання, він повинен дорівнювати одному з його блоків, звідки випливає, що він має бути непарним циклом і не бути графом Бержа. З тієї ж причини мінімальний недосконалий граф, доповнення якого має 2-з'єднання, не може бути графом Бержа.

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

Однорідні пари пов'язані з графа. Це розкладання графа на три підмножини image, такі, що image і image разом містять щонайменше три вершини, image містить щонайменше дві вершини, а для кожної вершини image з image і будь-якого image з {1,2} або image суміжна всім вершинам у image, або жодній із них. Неможливо для мінімального недосконалого графа мати однорідну пару. Після доведення сильної гіпотези про досконалі графи Чудновська спростила доведення, показавши, що однорідні пари можна виключити з набору декомпозицій, використовуваних у доведенні.

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

Примітки

  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 // . — 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 // . — 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 // . — 1972a. — Т. 2, вип. 3. — С. 253–267. — DOI:10.1016/0012-365X(72)90006-4.
  • László Lovász. A characterization of perfect graphs // . — 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 // . — 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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Silna teorema pro doskonali grafi ce harakterizaciya zaboronenimi grafami doskonalih grafiv yak tochno tih grafiv yaki ne mayut ni neparnih dir porodzhenih cikliv neparnoyi dovzhini ni neparnih antidir dopovnen neparnim diram Gipotezu visloviv en 1961 roku Dovedennya Mariyi Chudnovskoyi en en ta en zayavleno 2002 roku ta opublikovano 2006 roku Za dovedennya silnoyi teoremi pro doskonali grafi avtori otrimali priz 10 000 vid Dzherarda Kornidzholsa z universitetu Karnegi Mellon ta Tverdzhennya teoremiDoskonalij graf ce graf u yakomu dlya bud yakogo porodzhenogo pidgrafa rozmir najbilshoyi kliki dorivnyuye najmenshomu chislu koloriv neobhidnih dlya rozfarbovuvannya grafa Doskonali grafi vklyuchayut dobre vidomi klasi grafiv dvochastkovi grafi hordalni grafi ta grafi porivnyannosti U pracyah 1961 i 1963 rokiv viznachayuchi vpershe cej klas grafiv en zauvazhiv sho doskonali grafi ne mozhut mistiti neparnoyi diri porodzhenogo pidgrafa u formi ciklu neparnoyi dovzhini p yat abo bilshe oskilki neparni diri mayut klikove chislo dva a hromatichne chislo tri Analogichno vin zauvazhiv sho doskonali grafi ne mozhut mistiti neparnih antidir porodzhenih pidgrafiv dopovnen neparnih dir neparna antidira z 2 k 1 displaystyle 2k 1 vershinami maye klikove chislo k ta hromatichne chislo k 1 displaystyle k 1 sho znovu zh nemozhlivo dlya doskonalih grafiv Grafi yaki ne mayut ni neparnih dir ni neparnih antidir stali vidomi yak grafi Berzha Berzh visloviv pripushennya sho bud yakij graf Berzha doskonalij abo ekvivalentno sho doskonali grafi ta grafi Berzha viznachayut toj samij klas grafiv Ce pripushennya bulo vidomim yak silna gipoteza pro doskonali grafi azh do yiyi dovedennya 2002 roku koli yiyi perejmenovano na silnu teoremu pro doskonali grafi Zv yazok zi slabkoyu teoremoyu pro doskonali grafiInsha gipoteza Berzha yaku doviv 1972 roku Laslo Lovas stverdzhuye sho dopovnennya bud yakogo doskonalogo grafa takozh doskonale Teorema stala vidomoyu yak teorema pro doskonali grafi abo shob vidriznyati yiyi vid silnoyi gipotezi teoremi pro doskonali grafi slabka teorema pro doskonali grafi Oskilki harakterizuvannya zaboronenimi grafami Berzha samodvoyiste slabka teorema pro doskonali grafi viplivaye negajno iz silnoyi teoremi pro doskonali grafi Ideyi dovedennyaDovedennya silnoyi teoremi pro doskonali grafi Chudnovskoyi zi spivavtorami spirayetsya nacherk yakij zaproponuvali 2001 roku Konforti Kornidzhols Robertson Sejmur i Tomas Za cim nacherkom bud yakij graf Berzha abo utvoryuye odin iz p yati tipiv bazovih blokiv specialni klasi doskonalih grafiv abo maye odnu z chotiroh inshih tipiv strukturnih dekompozicij na prostishi grafi Minimalnij nedoskonalij graf Berzha ne mozhe mati zhodnoyi z cih dekompozicij zvidki viplivaye sho kontrprikladu teoremi ne mozhe isnuvati Cya ideya bula gruntuyetsya na gipotezi pro strukturnu dekompoziciyu podibnih tipiv z yakoyi viplivala b silna gipoteza pro doskonali grafi ale gipoteza ne viyavilasya spravedlivoyu P yat osnovnih klasiv doskonalih grafiv sho utvoryuyut osnovni vipadki ciyeyi strukturnoyi dekompoziciyi ce dvochastkovi grafi reberni grafi dvochastkovih grafiv dopovnennya dvochastkovih grafiv dopovnennya rebernih grafiv dvochastkovih grafiv i podvijni rozsheplyuvani grafi Legko bachiti sho dvochastkovi grafi doskonali u bud yakomu netrivialnomu porodzhenomu pidgrafi yak klikove chislo i hromatichne chislo rivni dvom Doskonalist dopovnen dvochastkovih grafiv ta dopovnen rebernih grafiv dvochastkovih grafiv ekvivalentna teoremi Keniga shodo rozmiriv najbilshih paruvan najbilshih nezalezhnih mnozhin ta najbilshih vershinnih pokrittiv u dvochastkovih grafah Doskonalist rebernih grafiv dvochastkovih grafiv mozhna sformulyuvati ekvivalentno yak fakt sho dvochastkovi grafi mayut hromatichnij indeks rivnij yih najbilshomu stepenyu sho doviv Kenig Takim chinom usi ci chotiri bazovi klasi doskonali Podvijni rozsheplyuvani grafi sporidneni rozsheplyuvanim grafam u tomu sho takozh mozhna pokazati yih doskonalist Chotiri tipi dekompoziciyi rozglyanutih u comu dovedenni ce 2 z yednannya dopovnennya 2 z yednan zbalansovani kosi rozbittya ta odnoridni pari 2 z yednannya ce rozbittya vershin grafa na dvi pidmnozhini zi vlastivistyu sho rebra yaki styaguyut rozriz mizh cimi dvoma pidmnozhinami utvoryuyut dvovershinni povni dvochastkovi grafi sho ne peretinayutsya vershinami Koli graf maye 2 z yednannya jogo mozhna rozklasti na porodzheni pidgrafi zvani blokami zaminoyu odniyeyi z dvoh pidmnozhin vershin najkorotshim shlyahom useredini ciyeyi pidmnozhini yakij z yednuye odin z dvoh povnih dvochastkovih grafiv z inshim Yaksho takogo shlyahu ne isnuye blok utvoryuyetsya natomist zaminoyu odniyeyi z pidmnozhin vershin dvoma vershinami po odnij dlya kozhnogo povnogo dvochastkovogo pidgrafa 2 z yednannya doskonale todi j lishe todi koli obidva jogo bloki doskonali Takim chinom yaksho minimalnij nedoskonalij graf maye 2 z yednannya vin povinen dorivnyuvati odnomu z jogo blokiv zvidki viplivaye sho vin maye buti neparnim ciklom i ne buti grafom Berzha Z tiyeyi zh prichini minimalnij nedoskonalij graf dopovnennya yakogo maye 2 z yednannya ne mozhe buti grafom Berzha Kose rozbittya ce rozbittya vershin grafa na dvi pidmnozhini odna z yakih porodzhuye nezv yaznij pidgraf a insha maye nezv yazne dopovnennya Hvatal visloviv gipotezu sho niyakij minimalnij kontrpriklad silnoyi gipotezi pro doskonali grafi ne mozhe mati kosogo rozbittya Chudnovska i spivavtori vveli deyaki tehnichni obmezhennya na kosi rozbittya i zmogli pokazati sho gipoteza Hvatala spravedliva dlya otrimuvanih zbalansovanih kosih rozbittiv Povna gipoteza ye naslidkom silnoyi teoremi pro doskonali grafi Odnoridni pari pov yazani z grafa Ce rozkladannya grafa na tri pidmnozhini V 1 V 2 V 3 displaystyle V 1 V 2 V 3 taki sho V 1 displaystyle V 1 i V 2 displaystyle V 2 razom mistyat shonajmenshe tri vershini V 3 displaystyle V 3 mistit shonajmenshe dvi vershini a dlya kozhnoyi vershini v displaystyle v z V 3 displaystyle V 3 i bud yakogo i displaystyle i z 1 2 abo v displaystyle v sumizhna vsim vershinam u V i displaystyle V i abo zhodnij iz nih Nemozhlivo dlya minimalnogo nedoskonalogo grafa mati odnoridnu paru Pislya dovedennya silnoyi gipotezi pro doskonali grafi Chudnovska sprostila dovedennya pokazavshi sho odnoridni pari mozhna viklyuchiti z naboru dekompozicij vikoristovuvanih u dovedenni Dovedennya sho bud yakij graf Berzha potraplyaye v odin iz p yati klasiv abo maye odin z chotiroh tipiv dekompoziciyi spirayetsya na rozbir okremih vipadkiv zgidno z yakim isnuye pevna konfiguraciya u grafi roztyazhka pidgraf yakij mozhna rozklasti na tri porodzheni shlyahi zgidno z pevnimi dodatkovimi obmezhennyami dopovnennya roztyazhki ta vlasne koleso konfiguraciya pov yazana z kolesom sho skladayetsya z porodzhenogo ciklu razom iz centralnoyu vershinoyu sumizhnoyu shonajmenshe z troma vershinami oboda i zadovolnyaye deyakim dodatkovim obmezhennyam Zalezhno vid togo chi isnuye vseredini zadanogo grafa Berzha roztyazhka dopovnennya roztyazhki abo vlasne koleso mozhna pokazati sho graf nalezhit do odnogo z bazovih klasiv abo mozhe buti piddanij dekompoziciyi Cej analiz vipadkiv zavershuye dovedennya PrimitkiMackenzie 2002 Cornuejols 2002 2009 Fulkerson Prizes 2011 s 1475 1476 Cornuejols 2002 s Gipoteza 5 1 Reed 1986 Hougardy 1991 Rusu 1997 Roussel Rusu Thuillier 2009 s rozdil 4 6 The first conjectures Konig 1916 Roussel Rusu Thuillier 2009 s Viznachennya 4 39 Cornuejols Cunningham 1985 Cornuejols 2002 s Teorema 3 2 i naslidok 3 3 Chvatal 1985 Seymour 2006 Roussel Rusu Thuillier 2009 s rozdil 4 7 The skew partition Cornuejols 2002 s Teoremi 4 1 i 4 2 Chvatal Sbihi 1987 Cornuejols 2002 s Teorema 4 10 Chudnovsky 2006 Cornuejols 2002 s Teoremi 5 4 5 5 5 6 Roussel Rusu Thuillier 2009 s Teorema 4 42 Literatura2009 Fulkerson Prizes Notices of the American Mathematical Society 2011 T 57 11 December S 1475 1476 ISSN 0002 9920 Claude Berge Farbung von Graphen deren samtliche bzw deren ungerade Kreise starr sind Wiss Z Martin Luther Univ Halle Wittenberg Math Natur Reihe 1961 T 10 S 114 Claude Berge Perfect graphs Six Papers on Graph Theory Calcutta Indian Statistical Institute 1963 S 1 21 Maria Chudnovsky Berge trigraphs Journal of Graph Theory 2006 T 53 vip 1 S 1 55 DOI 10 1002 jgt 20165 Maria Chudnovsky Neil Robertson Paul Seymour Robin Thomas The strong Annals of Mathematics 2006 T 164 vip 1 S 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 T 97 vip 1 2 S 405 422 Series B DOI 10 1007 s10107 003 0449 8 Vaclav Chvatal Star cutsets and perfect graphs Journal of Combinatorial Theory 1985 T 39 vip 3 S 189 199 Series B DOI 10 1016 0095 8956 85 90049 8 Vaclav Chvatal Najiba Sbihi Bull free Berge graphs are perfect 1987 T 3 vip 2 S 127 139 DOI 10 1007 BF01788536 Gerard Cornuejols The strong perfect graph conjecture Proceedings of the International Congress of Mathematicians Vol III Beijing 2002 Beijing Higher Ed Press 2002 S 547 559 Arhivna kopiya na sajti Wayback Machine Gerard Cornuejols Cunningham W H Compositions for perfect graphs 1985 T 55 vip 3 S 245 254 DOI 10 1016 S0012 365X 85 80001 7 Hougardy S Counterexamples to three conjectures concerning perfect graphs Grenoble France Laboratoire Artemis IMAG Universita Joseph Fourier 1991 Technical Report RR870 M Yak procitovano v statti Roussel Rusu Thuillier 2009 Denes Konig Grafok es alkalmazasuk a determinansok es a halmazok elmeletere Matematikai es Termeszettudomanyi Ertesito 1916 T 34 S 104 119 Laszlo Lovasz Normal hypergraphs and the perfect graph conjecture 1972a T 2 vip 3 S 253 267 DOI 10 1016 0012 365X 72 90006 4 Laszlo Lovasz A characterization of perfect graphs 1972b T 13 vip 2 S 95 98 Series B DOI 10 1016 0095 8956 72 90045 7 Dana Mackenzie Mathematics Graph theory uncovers the roots of perfection Science 2002 T 297 vip 5578 July S 38 DOI 10 1126 science 297 5578 38 PMID 12098683 Bruce A Reed A semi strong perfect graph theorem Montreal Quebec Canada Department of Computer Science McGill University 1986 Ph D thesis Kak procitirovano v state Roussel Rusu Thuillier 2009 Roussel F Rusu I Thuillier H The strong perfect graph conjecture 40 years of attempts and its resolution 2009 T 309 vip 20 S 6092 6113 DOI 10 1016 j disc 2009 05 024 Irena Rusu Building counterexamples Discrete Mathematics 1997 T 171 vip 1 3 S 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 Mathematiciens 2006 Vip 109 S 69 83 PosilannyaThe Strong Perfect Graph Theorem Vaclav Chvatal Weisstein Eric W Silna teorema pro doskonali grafi angl na sajti Wolfram MathWorld

Дата публікації:
Топ