Perfekt gráfok
A MathWikiből
(Változatok közti eltérés)
| 1. sor: | 1. sor: | ||
| − | Egy <math>G</math> | + | Egy <math>G</math> gráfot akkor nevezunk perfektnek, ha <math>\chi(G)</math> = <math>\omega(G)</math> és ezentul <math>G</math> minden feszitett <math>G'</math> részgráfjára teljesul, hogy <math>\chi(G')</math> = <math>\omega(G')</math>. |
| − | == | + | == Tétel 1 == |
| − | Minden | + | Minden [[Páros gráfok|páros gráf]] perfekt. |
| − | == | + | == Tétel 2 == |
| − | Minden | + | Minden [[intervallumgráf]] perfekt. |
A lap 2007. április 30., 23:00-kori változata
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.
