Perfekt grafsats

Två kompletterande perfekta grafer

Inom grafteorin säger László Lovász ' perfekta grafsats ( 1972a , 1972b ) att en oriktad graf är perfekt om och endast om dess komplementgraf också är perfekt. Detta resultat hade antagits av Berge ( 1961 , 1963 ), och det kallas ibland den svaga perfekta grafsatsen för att skilja den från den starka perfekta grafsatsen som karakteriserar perfekta grafer genom deras förbjudna inducerade subgrafer .

Påstående

En perfekt graf är en oriktad graf med egenskapen att, i var och en av dess inducerade subgrafer , storleken på den största klicken är lika med det minsta antalet färger i en färgning av subgrafen. Perfekta grafer inkluderar många viktiga grafer, inklusive tvådelade grafer , ackordsgrafer och jämförbarhetsgrafer .

Komplementet av en graf har en kant mellan två hörn om och endast om den ursprungliga grafen inte har en kant mellan samma två hörn. Således blir en klick i den ursprungliga grafen en oberoende uppsättning i komplementet och en färgning av den ursprungliga grafen blir ett klickskydd av komplementet.

Den perfekta grafsatsen säger:

Komplementet av en perfekt graf är perfekt.

På motsvarande sätt, i en perfekt graf, är storleken på den maximala oberoende uppsättningen lika med det minsta antalet klick i ett klickomslag.

Exempel

En cykel med sju vertex och dess komplement, antihålet med sju vertex, som i varje fall visar en optimal färgning och en maximal klick (visas med kraftiga kanter). Eftersom ingen av graferna använder ett antal färger lika med dess klickstorlek, är ingen av dem perfekt.

Låt G vara en cykelgraf med udda längd större än tre (ett så kallat "udda hål"). Då G minst tre färger i valfri färg, men har ingen triangel, så den är inte perfekt. Enligt den perfekta grafsatsen måste komplementet till G (ett "udda antihål") därför inte heller vara perfekt. Om G är en cykel med fem hörn är den isomorf till dess komplement , men den här egenskapen är inte sann för längre udda cykler, och det är inte lika trivialt att beräkna klicktalet och kromatiska talet i ett udda antihål som det är i ett udda hål. Som den starka perfekta grafsatsen säger, visar sig de udda hålen och udda antihålen vara de minimala förbjudna inducerade subgraferna för de perfekta graferna.

Ansökningar

I en icke-trivial tvådelad graf är det optimala antalet färger (per definition) två, och (eftersom tvådelade grafer är triangelfria ) är den maximala klickstorleken också två. Dessutom förblir varje inducerad subgraf i en tvådelad graf tvådelad. Därför är tvådelade grafer perfekta. I med n -vertex tar ett minimum av klicktäckning formen av en maximal matchning tillsammans med en extra klick för varje omatchad vertex, med storlek n − M , där M är matchningens kardinalitet. I det här fallet innebär alltså den perfekta grafsatsen Kőnigs teorem att storleken på en maximal oberoende mängd i en tvådelad graf också är n − M , ett resultat som var en stor inspiration för Berges formulering av teorin om perfekta grafer.

Mirskys teorem som karakteriserar höjden av en partiellt ordnad mängd i termer av uppdelningar i antikedjor kan formuleras som perfektionen av jämförbarhetsgrafen för den partiellt ordnade mängden, och Dilworths teorem som karakteriserar bredden av en partiellt ordnad mängd i termer av uppdelningar i kedjor kan formuleras som perfektionen av komplementen till dessa grafer. Således kan den perfekta grafsatsen användas för att bevisa Dilworths sats från det (mycket enklare) beviset för Mirskys sats, eller vice versa.

Lovász bevis

För att bevisa den perfekta grafsatsen använde Lovász en operation för att ersätta hörn i en graf med klickar; det var redan känt för Berge att, om en graf är perfekt, är den graf som bildas av denna ersättningsprocess också perfekt. Varje sådan ersättningsprocess kan delas upp i upprepade steg med fördubbling av en vertex. Om det dubbla hörnet tillhör en maximal klick i grafen, ökar det både klicknumret och det kromatiska talet med en. Om däremot den dubblade vertexen inte tillhör en maximal klick, bilda en graf H genom att ta bort hörnen med samma färg som den dubblade vertexen (men inte själva dubbla vertexen) från en optimal färgning av den givna grafen . De borttagna hörnen möter varje maximal klick, så H har klicknummer och kromatiskt nummer ett mindre än det för den givna grafen. De borttagna hörnen och den nya kopian av det dubbla hörnet kan sedan läggas tillbaka som en enda färgklass, vilket visar att i detta fall lämnar dubbleringssteget det kromatiska talet oförändrat. Samma argument visar att dubblering bevarar likheten mellan klicknumret och det kromatiska talet i varje inducerad subgraf i den givna grafen, så varje dubbleringssteg bevarar grafens perfektion.

Givet en perfekt graf G , bildar Lovász en graf G * genom att ersätta varje vertex v med en klick av t v hörn, där t v är antalet distinkta maximala oberoende uppsättningar i G som innehåller v . Det är möjligt att korrespondera var och en av de distinkta maximala oberoende mängderna i G med en av de maximala oberoende mängderna i G *, på ett sådant sätt att de valda maximala oberoende mängderna i G * alla är disjunkta och varje vertex av G * visas i en enstaka vald uppsättning; det vill säga, G * har en färgning där varje färgklass är en maximal oberoende uppsättning. Denna färgning är nödvändigtvis en optimal färgning av G *. Eftersom G är perfekt, så är G * det också, och därför har den en maximal klick K * vars storlek är lika med antalet färger i denna färg, vilket är antalet distinkta maximala oberoende uppsättningar i G ; nödvändigtvis innehåller K * en distinkt representant för var och en av dessa maximala oberoende uppsättningar. Motsvarande mängd K av hörn i G (de hörn vars expanderade klick i G * skär K *) är en klick i G med egenskapen att den skär varje maximalt oberoende mängd i G . Därför har grafen som bildas från G genom att ta bort K ett klicktäckningsnummer som högst en mindre än klicknumret för G och ett oberoende nummer minst ett mindre än oberoendetalet för G , och resultatet följer av induktion på detta nummer.

Relation till den starka perfekta grafsatsen

Den starka perfekta grafsatsen av Chudnovsky et al. (2006) säger att en graf är perfekt om och endast om ingen av dess inducerade subgrafer är cykler med udda längder större än eller lika med fem, eller deras komplement. Eftersom denna karakterisering är opåverkad av grafkomplementering, innebär den omedelbart den svaga perfekta grafsatsen.

Generaliseringar

Cameron, Edmonds & Lovász (1986) bevisade att om kanterna på en komplett graf är uppdelade i tre subgrafer på ett sådant sätt att var tredje hörn inducerar en sammankopplad graf i en av de tre subgraferna, och om två av subgraferna är perfekta , då är den tredje subgrafen också perfekt. Den perfekta grafsatsen är specialfallet för detta resultat när en av de tre subgraferna är den tomma grafen .

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Perfect_graph_theorem&oldid=1135929956 "