Lovash Perfect Graph Theorem [1] [2] siger, at en urettet graf er perfekt , hvis og kun hvis dens komplement også er perfekt. Dette udsagn kom til udtryk i form af Berges formodning [3] [4] og udsagnet kaldes nogle gange for den svage perfekte grafsætning, for ikke at forveksle med den strenge perfekte grafsætning [5] , som beskriver perfekte grafer ved deres forbudte genererede undergrafer .
En perfekt graf er en urettet graf, i enhver genereret undergraf , hvis størrelse på dens største klike er lig med det mindste antal undergraffarvefarver . Perfekte grafer omfatter mange vigtige klasser af grafer, herunder todelte grafer , akkordgrafer og sammenlignelighedsgrafer .
Komplementet af en graf har en kant mellem to hjørner, hvis og kun hvis den originale graf ikke har en sådan kant. Kliken i den originale graf bliver således et selvstændigt sæt i komplementet, og farvelægningen af den originale graf bliver komplementets klikomslag .
Den perfekte grafsætning siger:
Komplementet af en perfekt graf er perfekt.Tilsvarende formulering: I en perfekt graf er størrelsen af det største uafhængige sæt lig med minimumsantallet af kliker i klikomslaget.
Lad G være en grafcyklus med en ulige længde større end tre (det såkaldte "ulige hul"). Så kræver hver farvning af G mindst tre farver, men der er ingen trekanter, så grafen er ikke perfekt. Ved perfekt grafsætning skal komplementet til grafen G ("det ulige antihul") derfor også være uperfekt. Hvis en graf G er en cyklus med fem hjørner, er den isomorf i forhold til dens komplement , men dette er ikke sandt for længere cyklusser. En ikke-triviel opgave er at beregne kliktallet og det kromatiske tal i et ulige antihul og et ulige hul. Som den strenge perfekte grafsætning siger , viser ulige huller og ulige antihuller sig at være de minimale forbudte inducerede undergrafer af perfekte grafer.
I en ikke-triviel todelt graf er det optimale antal farver (per definition) to, og (da todelte grafer ikke indeholder trekanter ) er den største klikstørrelse også to. Enhver genereret undergraf af en todelt graf forbliver således todelt. Således er todelte grafer perfekte. I todelte grafer med n toppunkter har den største klikdækning form af den største matchende , sammen med en ekstra klik for hvert udækket toppunkt af størrelse n − M , hvor M er antallet af elementer i matchningen. I dette tilfælde indebærer den perfekte grafsætning Königs sætning om, at størrelsen af den maksimale uafhængige mængde i en todelt graf i en todelt graf også er n − M [6] , et resultat der var den vigtigste drivkraft for Berges formulering af teori om perfekte grafer.
Mirskys sætning , der beskriver højden af en poset i form af opdeling i antikæder , kan formuleres som en perfektion af sammenlignelighedsgrafen for en poset, og Dilworths teoremer , der beskriver bredden af en poset i form af opdeling i kæder, kan formuleres som en perfektion af komplementerne til disse grafer. Således kan den perfekte grafsætning bruges til at bevise Dilworths sætning ved at stole på det (enklere) bevis for Mirskys sætning eller omvendt [7] .
For at bevise sætningen om perfekte grafer brugte Lovash operationen med at erstatte toppunkter i en graf med kliker. Berge vidste allerede, at hvis grafen er perfekt, vil grafen opnået ved en sådan udskiftning også være perfekt [8] . Enhver sådan udskiftningsproces kan opdeles i gentagne vertex-duplikeringstrin. Hvis det duplikerede toppunkt tilhører den største klike på grafen, øger det kliktallet og det kromatiske tal med én. Hvis det duplikerede toppunkt derimod ikke hører til den største klike, skal du danne grafen H ved at fjerne toppunkter af samme farve som det duplikerede (men ikke selve det duplikerede toppunkt) fra grafens optimale farve. De hjørner, der skal fjernes, indgår i alle største kliker, således at H har antallet af kliker og det kromatiske tal et mindre end i den oprindelige graf. Fjernede hjørner og nye kopier af duplikerede hjørner kan tilføjes til en enkelt farveklasse, hvilket viser, at duplikeringstrinnet ikke ændrer det kromatiske tal. De samme argumenter viser, at fordobling holder antallet af kliker lig med det kromatiske tal i hver genereret undergraf i den givne graf, således at hvert trin i fordoblingen holder grafen perfekt [9] .
Givet en perfekt graf G , genererer Lovash en graf G * ved at erstatte hvert toppunkt v med en klike med t v hjørner, hvor t v er antallet af distinkte maksimale distinkte sæt i G indeholdende v . Man kan til hver af de forskellige maksimale uafhængige mængder i G associere en maksimal uafhængig mængde i G * på en sådan måde, at de uafhængige mængder i G * alle er usammenhængende og hvert toppunkt af G * optræder i den eneste valgte mængde. Det vil sige, at G * har en farve, hvor hver farveklasse er et maksimalt uafhængigt sæt. Nødvendigvis vil denne farvning være en optimal farvning af G *. Da G er perfekt, er G * det også, og så har den en maksimal klike K *, hvis størrelse er lig med antallet af farver i denne farve, hvilket er lig med antallet af forskellige maksimale uafhængige sæt i G . Nødvendigvis indeholder K * en forskellig repræsentation for hver af disse maksimale sæt. Det tilsvarende sæt K af knudepunkter i G (hjørnepunkter, hvis udvidede kliker i G * skærer K *) er en klike i G med den egenskab, at den skærer ethvert maksimalt uafhængigt sæt i G . Grafen dannet ud fra G ved at fjerne K har således et kliknummer, der ikke er større end kliktallet for G uden en, og uafhængighedstallet er mindst én mindre end uafhængighedstallet for G . Resultatet følger af induktion på dette tal [10]
Den stærke sætning om perfekte grafer af Chudnovskaya, Robertson, Seymour og Thomas [11] siger, at en graf er perfekt, hvis og kun hvis ingen af de genererede undergrafer er en cyklus med en ulige længde større end eller lig med fem, og heller ikke er komplementet til en sådan cyklus. Da en sådan beskrivelse er ufølsom over for grafkomplementoperationen, følger den svage perfekte grafsætning med det samme.
Cameron, Edmonds og Lovasz [12] beviste, at hvis kanterne af en komplet graf er opdelt i tre undergrafer på en sådan måde, at tre spidser genererer en forbundet graf i en af de tre undergrafer, og hvis to af undergraferne er perfekte , så er den tredje undergraf også perfekt. Den perfekte grafsætning er et specialtilfælde af dette resultat, når en af de tre grafer er den tomme graf .