Stark perfekt grafsats

I grafteorin är den starka perfekta grafsatsen en förbjuden grafkarakterisering av de perfekta graferna som exakt de grafer som varken har udda hål (udda längd- inducerade cykler med längd minst 5) eller udda antihål (komplement till udda hål). Det antogs av Claude Berge 1961. Ett bevis av Maria Chudnovsky , Neil Robertson , Paul Seymour och Robin Thomas tillkännagavs 2002 och publicerades av dem 2006.

Beviset på den starka perfekta grafsatsen vann för sina författare ett pris på 10 000 dollar som erbjöds av Gérard Cornuéjols från Carnegie Mellon University och 2009 års Fulkerson-pris .

Påstående

En perfekt graf är en graf där, för varje inducerad subgraf , storleken på den maximala klicken är lika med det minsta antalet färger i en färgning av grafen; perfekta grafer inkluderar många välkända grafer, inklusive tvådelade grafer , ackordsgrafer och jämförbarhetsgrafer . I sina arbeten från 1961 och 1963 som för första gången definierade denna klass av grafer, Claude Berge att det är omöjligt för en perfekt graf att innehålla ett udda hål, en inducerad subgraf i form av en udda cykelgraf med längd fem eller mer, eftersom udda hål har klick nummer två och kromatisk nummer tre. På liknande sätt observerade han att perfekta grafer inte kan innehålla udda antihål, inducerade subgrafer som är komplementära till udda hål: ett udda antihål med 2 k + 1 hörn har klicknummer k och kromatiskt nummer k + 1, vilket återigen är omöjligt för perfekta grafer. Graferna som varken hade udda hål eller udda antihål blev kända som Berge-graferna.

Berge antog att varje Berge-graf är perfekt, eller motsvarande att de perfekta graferna och Berge-graferna definierar samma klass av grafer. Detta blev känt som den starka perfekta grafförmodan, fram till dess bevis 2002, då den döptes om till den starka perfekta grafsatsen.

Relation till den svaga perfekta grafsatsen

En annan gissning om Berge, bevisad 1972 av László Lovász , är att komplementet till varje perfekt graf också är perfekt. Detta blev känt som den perfekta grafsatsen , eller (för att skilja den från den starka perfekta grafsatsen) den svaga perfekta grafsatsen. Eftersom Berges förbjudna grafkarakterisering är självkomplementär, följer den svaga perfekta grafsatsen omedelbart från den starka perfekta grafsatsen.

Bevis idéer

Beviset för den starka perfekta grafsatsen av Chudnovsky et al. följer en kontur som antogs 2001 av Conforti, Cornuéjols, Robertson, Seymour och Thomas, enligt vilken varje Berge-graf antingen bildar en av fem typer av grundläggande byggstenar (speciella klasser av perfekta grafer) eller så har den en av fyra olika typer av strukturell nedbrytning till enklare grafer. En minimalt imperfekt Berge-graf kan inte ha någon av dessa nedbrytningar, varav det följer att inget motexempel till satsen kan existera. Denna idé baserades på tidigare förmodade strukturella nedbrytningar av liknande typ som skulle ha inneburit den starka perfekta grafförmodan men visade sig vara falsk.

De fem grundläggande klasserna av perfekta grafer som bildar basfallet för denna strukturella nedbrytning är tvådelade grafer , linjediagram av tvådelade grafer, komplementära grafer för tvådelade grafer, komplement till linjediagram för tvådelade grafer och dubbeldelade grafer. Det är lätt att se att tvådelade grafer är perfekta: i alla icke-triviala inducerade subgrafer är klicknumret och kromatiskt tal båda två och därför båda lika. Perfektionen av komplement till tvådelade grafer, och komplement till linjediagram av tvådelade grafer, är båda ekvivalenta med Kőnigs sats som relaterar storleken på maximala matchningar , maximala oberoende uppsättningar och minimala vertextäckningar i tvådelade grafer. Perfektionen av linjegrafer av tvådelade grafer kan anges på samma sätt som det faktum att tvådelade grafer har ett kromatiskt index som är lika med deras maximala grad , bevisat av Kőnig (1916) . Således är alla fyra av dessa grundläggande klasser perfekta. De dubbla delade graferna är en släkting till de delade graferna som också kan visas vara perfekta.

De fyra typerna av sönderdelningar som beaktas i detta bevis är 2-fogar, komplement till 2-fogar, balanserade skevpartitioner och homogena par.

En 2-join är en uppdelning av hörn av en graf i två delmängder, med egenskapen att kanterna som spänner över snittet mellan dessa två delmängder bildar två vertex-disjunkta kompletta tvådelade grafer . När en graf har en 2-koppling, kan den brytas upp i inducerade subgrafer som kallas "block", genom att ersätta en av de två delmängderna av hörn med en kortaste väg inom den delmängden som förbinder en av de två kompletta tvådelade graferna till den andra; när ingen sådan väg existerar, bildas blocket istället genom att ersätta en av de två delmängderna av hörn med två hörn, en för varje komplett tvådelad subgraf. En 2-join är perfekt om och bara om dess två block är perfekta. Därför, om en minimalt imperfekt graf har en 2-koppling, måste den vara lika med ett av dess block, av vilket det följer att det måste vara en udda cykel och inte Berge. Av samma anledning kan en minimalt imperfekt graf vars komplement har en 2-join inte vara Berge.

En skev partition är en partition av en grafs hörn i två delmängder, av vilka en inducerar en frånkopplad subgraf och den andra har ett frånkopplat komplement; Chvátal (1985) hade gissat att inget minimalt motexempel till den starka perfekta grafförmodan kunde ha en skev partition. Chudnovsky et al. introducerade några tekniska begränsningar på skeva partitioner, och kunde visa att Chvátals gissning är sann för de resulterande "balanserade snedpartitionerna". Den fullständiga gissningen är en följd av den starka perfekta grafsatsen.

Ett homogent par är relaterat till en modulär uppdelning av en graf. Det är en uppdelning av grafen i tre delmängder V 1 , V 2 och V 3 så att V 1 och V 2 tillsammans innehåller minst tre hörn, V 3 innehåller minst två hörn, och för varje vertex v i V 3 och varje i i {1,2} är antingen v intill alla hörn i V i eller ingen av dem. Det är inte möjligt för en minimalt imperfekt graf att ha ett homogent par. Efter beviset på den starka perfekta grafförmodan, Chudnovsky (2006) den genom att visa att homogena par kunde elimineras från uppsättningen av nedbrytningar som användes i beviset.

Beviset på att varje Berge-graf faller i en av de fem grundläggande klasserna eller har en av de fyra typerna av nedbrytning följer en fallanalys, beroende på om vissa konfigurationer finns i grafen: en "sträckare", en subgraf som kan dekomponeras i tre inducerade banor som omfattas av vissa ytterligare begränsningar, komplementet av en bår, och ett "riktigt hjul", en konfiguration relaterad till ett hjuldiagram , bestående av en inducerad cykel tillsammans med en navpunkt som gränsar till minst tre cykelspetsar och som lyder flera ytterligare begränsningar. För varje tänkbart val av om en bår eller dess komplement eller ett riktigt hjul finns inom den givna Berge-grafen, kan grafen visas vara i en av grundklasserna eller vara nedbrytbar. Denna fallanalys fullbordar beviset.

Anteckningar

externa länkar

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