P-Critical graph

Материал из WikiGrapp
Версия от 15:44, 15 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''<math>p</math>-Critical graph''' --- <math>p</math>-критический граф. A graph <math>G</math> is '''<math>p</math>-critical''' if <math>G</math> is…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ p }[/math]-Critical graph --- [math]\displaystyle{ p }[/math]-критический граф. A graph [math]\displaystyle{ G }[/math] is [math]\displaystyle{ p }[/math]-critical if [math]\displaystyle{ G }[/math] is not perfect but every proper induced subgraph of [math]\displaystyle{ G }[/math] is perfect. The celebrated Strong Perfect Graph Conjecture (SPGC) of C. Berge states that [math]\displaystyle{ p }[/math]-critical graphs are only [math]\displaystyle{ C_{2n+1} }[/math] and [math]\displaystyle{ C_{2n+1}^{c} }[/math], [math]\displaystyle{ n \geq 2 }[/math].