Perfekt gráfok
A MathWikiből
A lap korábbi változatát látod, amilyen Kristofh (vitalap | szerkesztései) 2007. április 30., 23:00-kor történt szerkesztése után volt.
Egy G gráfot akkor nevezunk perfektnek, ha χ(G) = ω(G) és ezentul G minden feszitett G' részgráfjára teljesul, hogy χ(G') = ω(G').
Tétel 1
Minden páros gráf perfekt.
Tétel 2
Minden intervallumgráf perfekt.
