Berge's conjecture

Материал из WikiGrapp
Версия от 13:26, 12 января 2012; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Berge's conjectureгипотеза Бержа.

In 1960, C.Berge conjectured that a graph is perfect iff none of its induced subgraphs is a [math]\displaystyle{ \,C_{2k+1} }[/math] or the complement of such a cycle, [math]\displaystyle{ k \geq 2 }[/math].

This conjecture is well-known as the Strong Perfect Graph Conjecture and is still open.

Литература

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