Perfecte graaf

Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf. Een geïnduceerde subgraaf bestaat uit een deelverzameling van de knopen van de graaf en alleen de zijden van de graaf tussen die knopen. Het cliquegetal is het aantal knopen in de grootste volledige subgraaf van een graaf. De naam perfecte graaf wordt toegeschreven aan de Franse wiskundige Claude Berge die die in 1963 in een artikel gebruikte.

Voorbeeld van een perfecte graaf. In vet is een geïnduceerde subgraaf aangeduid met drie knopen. Het is een clique met chromatisch getal 3. Voor elke subgraaf van deze graaf is het cliquegetal gelijk aan het chromatisch getal.

Men kan in polynomiale tijd bepalen of een gegeven graaf een perfecte graaf is en ook in polynomiale tijd van een perfecte graaf het chromatisch getal, cliquegetal of stabiliteitsgetal berekenen, terwijl dit in het algemene geval een NP-compleet probleem is.

Er komen in de grafentheorie verschillende perfecte grafen voor, bijvoorbeeld:

• bipartiete grafen
• chordale grafen
• volledige grafen

Stelling

Claude Berge formuleerde in 1961 het vermoeden, dat een graaf $G$ een perfecte graaf is dan en slechts dan als $G$ geen geïnduceerde subgraaf bevat die een oneven cykel van lengte 5 of meer is, of het complement van zo een cykel is. Het bewijs van dit vermoeden werd in 2002 aangekondigd en in 2006 gepubliceerd in een artikel van 179 bladzijden. Het vermoeden staat nu bekend als de sterke stelling over perfecte grafen.

De zwakke stelling over perfecte grafen zegt dat de complementgraaf van een perfecte graaf ook een perfecte graaf is. Dit was ook een vermoeden van Claude Berge, dat in 1972 bewezen is door László Lovász.

Voetnoten