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.

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