P-Critical graph

[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].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.