Silný dohad o dokonalých grafech

Silná domněnka dokonalého grafu  je čárový graf charakterizující dokonalé grafy jako přesně ty grafy, které nemají ani liché díry ( cykly generované lichou délkou ) ani liché antidíry (doplňky k lichým dírám). Tuto domněnku učinil Berge v roce 1961. Důkaz Marie Chudnovské , Neila Robertsona , Paula Seymoura a Robina Thomase byl uveden v roce 2002 [1] [2] a jimi zveřejněny v roce 2006.

Za prokázání silné věty o dokonalém grafu autoři obdrželi cenu 10 000 $ od Gerarda Cornijolse z Carnegie Mellon University [1] a Fulkersonovu cenu za rok 2009 [3] .

Prohlášení věty

Dokonalý graf  je graf, ve kterém pro jakýkoli vygenerovaný podgraf je velikost největší kliky rovna nejmenšímu počtu barev potřebných k obarvení grafu. Dokonalé grafy zahrnují dobře známé třídy grafů, jako jsou bipartitní grafy , akordické grafy a grafy srovnatelnosti . V letech 1961 a 1963, když poprvé definoval tyto třídy grafů, Berge poznamenal, že dokonalé grafy nemohou obsahovat lichou díru, generovaný podgraf ve formě cyklu o liché délce pět nebo více, protože liché díry mají klika číslo dvě a chromatická číslo tři. Podobně si všiml, že dokonalé grafy nemohou obsahovat liché antidíry, generované podgrafy komplementární k lichým dírám – lichá antidíra s vrcholy má klikové číslo k a chromatické číslo , což je opět nemožné pro dokonalé grafy. Grafy bez lichých děr ani lichých antiděr se staly známými jako Bergeovy grafy.

Berge se domníval, že jakýkoli Bergeův graf je dokonalý, nebo ekvivalentně, že dokonalé grafy a Bergeovy grafy definují stejnou třídu grafů. Tato domněnka byla známá jako domněnka silného dokonalého grafu až do svého důkazu v roce 2002, kdy byla přejmenována na větu o silném dokonalém grafu.

Souvislost se slabou větou o dokonalém grafu

Další Bergeho domněnka, dokázaná v roce 1972 Laszlo Lovasem , uvádí, že doplněk každého dokonalého grafu je také dokonalý. Věta se stala známou jako věta o dokonalém grafu nebo (pro odlišení od věty o silné domněnce / větě o dokonalém grafu) jako slabá věta o dokonalém grafu. Vzhledem k tomu, že charakterizace zakázanými Bergeovými grafy je samoduální, slabá věta o dokonalém grafu bezprostředně vyplývá ze silné věty o dokonalém grafu.

Nápady na důkaz

Důkaz silné věty o dokonalém grafu od Chudnovskaya a kol., sleduje osnovu navrženou v roce 2001 Confortim, Cornijolsem, Robertsonem, Seymourem a Thomasem. Podle této osnovy každý Bergeův graf tvoří buď jeden z pěti typů základních bloků (speciální třídy dokonalých grafů), nebo má jeden ze čtyř dalších typů strukturálních rozkladů na jednodušší grafy. Minimálně nedokonalý Bergeův graf nemůže mít žádný z těchto rozkladů, což znamená, že protipříklad k větě nemůže existovat [4] . Tato myšlenka byla založena na dohadu strukturního rozkladu podobných typů, ze kterého by vyplývala silná domněnka o dokonalých grafech, ale domněnka se neukázala jako pravdivá [5] [6] [7] [8] .

Pět hlavních tříd dokonalých grafů, které tvoří hlavní případy tohoto strukturálního rozkladu, jsou bipartitní grafy , spojnicové grafy bipartitních grafů, doplňky bipartitních grafů, doplňky spojnicových grafů bipartitních grafů a dvojité rozdělené grafy. Je snadné vidět, že bipartitní grafy jsou dokonalé – v každém netriviálním generovaném podgrafu se jak počet kliky, tak chromatické číslo rovná dvěma. Dokonalost doplňků bipartitních grafů a doplňků spojnicových grafů bipartitních grafů je ekvivalentní Königově větě o velikostech největších shod , největších nezávislých množin a největších krytů vrcholů v bipartitních grafech. Dokonalost spojnicových grafů bipartitních grafů lze ekvivalentně formulovat jako skutečnost, že bipartitní grafy mají chromatický index rovný jejich největší mohutnosti , jak dokázal König [9] . Všechny čtyři tyto základní třídy jsou tedy dokonalé. Dvojité dělené grafy souvisí s dělenými grafy v tom, že mohou být také ukázány jako dokonalé [10] .

Čtyři typy rozkladu uvažované v tomto důkazu jsou 2-spojení, 2-spojení doplňky, vyvážené šikmé oddíly a homogenní páry.

2-spojení je rozdělení vrcholů grafu do dvou podmnožin s tou vlastností, že hrany, které stahují řez mezi těmito dvěma podmnožinami, tvoří dvouvrcholové neprotínající se (ve vrcholech) kompletní bipartitní grafy . Když má graf 2-spojení, lze jej rozložit na vygenerované podgrafy zvané „bloky“ nahrazením jedné ze dvou podmnožin vrcholů nejkratší cestou v rámci této podmnožiny, která spojuje jeden ze dvou úplných bipartitních grafů s druhým. Pokud žádná taková cesta neexistuje, blok se vytvoří nahrazením jedné z podmnožin vrcholů dvěma vrcholy, jedním pro každý úplný bipartitní podgraf. 2-join je perfektní tehdy a jen tehdy, když jsou dokonalé oba jeho bloky. Pokud má tedy minimální nedokonalý graf 2-spojení, musí se rovnat jednomu z jeho bloků, což znamená, že se musí jednat o lichý cyklus a ne o Bergeův graf. Ze stejného důvodu nemůže být Bergeovým grafem minimální nedokonalý graf, jehož doplněk má 2-spojení [11] [12] .

Šikmý oddíl  je rozdělení vrcholů grafu na dvě podmnožiny, z nichž jedna generuje nesouvislý podgraf a druhá má odpojený doplněk. Chvátal [13] se domníval, že žádný minimální protipříklad k domněnce silného dokonalého grafu nemůže mít šikmé rozdělení. Chudnovskaya et al zavedli některá technická omezení na šikmé oddíly a byli schopni ukázat, že Chvátalova domněnka platí pro výsledné „vyvážené šikmé oddíly“. Úplná domněnka je důsledkem silné věty o dokonalém grafu [14] [15] [16] .

Homogenní dvojice souvisí s modulárním rozkladem grafu. Jedná se o rozklad grafu na tři podmnožiny tak, že a společně obsahují alespoň tři vrcholy, obsahuje alespoň dva vrcholy a pro každý vrchol v a libovolné i z {1,2} buď v sousedí se všemi vrcholy v , nebo ani jeden z nich. Je nemožné, aby minimální nedokonalý graf měl homogenní pár [17] [18] . Po prokázání silné domněnky dokonalého grafu Chudnovskaya [19] zjednodušila důkaz tím, že ukázala, že homogenní páry lze vyloučit z množiny rozkladů použitých v důkazu.

Důkaz, že jakýkoli Bergeův graf spadá do jedné z pěti tříd nebo má jeden ze čtyř typů rozkladu, následuje po rozboru jednotlivých případů, podle kterých existuje v grafu určitá konfigurace – „roztažení“, podgraf, který může být rozložen do tří generovaných drah podle určitých dalších omezení, rozšíření rozšíření a "vlastního kola", což je konfigurace spojená s kolem sestávající z generovaného cyklu s centrálním vrcholem sousedícím s alespoň třemi vrcholy ráfku a splňující některá další omezení. V závislosti na tom, zda v daném Bergeově grafu existuje úsek, doplněk úseku nebo správné kolo, lze ukázat, že graf patří do jedné ze základních tříd, nebo jej lze rozložit [20] [21] . Tato případová studie doplňuje důkaz.

Poznámky

  1. ↑ 12 Mackenzie , 2002 .
  2. ↑ Cornuejols, 2002 .
  3. ↑ Fulkersonovy ceny 2009, 2011 , str. 1475–1476
  4. ↑ Cornuejols, 2002 , str. Dohad 5.1.
  5. ↑ Reed, 1986 .
  6. ↑ Hougardy, 1991 .
  7. ↑ Rusu, 1997 .
  8. ↑ Roussel, Rusu, Thuillier, 2009 , s. část 4.6 První dohady.
  9. ↑ Kőnig, 1916 .
  10. ↑ Roussel, Rusu, Thuillier, 2009 , s. Definice 4.39.
  11. ↑ Cornuejols, Cunningham, 1985 .
  12. ↑ Cornuejols, 2002 , str. Věta 3.2 a důsledek 3.3.
  13. ↑ Chvátal, 1985 .
  14. ↑ Seymour, 2006 .
  15. ↑ Roussel, Rusu, Thuillier, 2009 , s. část 4.7 Zkosený oddíl.
  16. ↑ Cornuejols, 2002 , str. Věty 4.1 a 4.2.
  17. ↑ Chvátal, Sbihi, 1987 .
  18. ↑ Cornuejols, 2002 , str. Věta 4.10.
  19. ↑ Chudnovsky, 2006 .
  20. ↑ Cornuejols, 2002 , str. Věty 5.4, 5.5, 5.6.
  21. ↑ Roussel, Rusu, Thuillier, 2009 , s. Věta 4.42.

Literatura

Odkazy