Perfekt gráf | mateking
 

Perfekt gráf

Ha egy $G$ gráf minden $G'$ feszített részgráfjára igaz, hogy

\( \omega (G') = \chi (G') \)

akkor a $G$ gráfot perfekt gráfnak nevezzük.

Ha egy gráf perfekt, akkor a kromatikus száma egyenlő a klikkszámával. Az állítás fordítva nem igaz, abból, hogy $\omega (G') = \chi (G')$ még nem következik, hogy a gráf perfekt.