Berge's conjecture: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Berge's conjecture''' --- гипотеза Бержа. In 1960, C.Berge conjectured that a graph is ''perfect'' iff none of its induced subgraphs is a <math>C_{…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Berge's conjecture''' | '''Berge's conjecture''' — ''[[гипотеза Бержа]].'' | ||
In 1960, C.Berge conjectured that a graph is ''perfect'' iff | In 1960, C.Berge conjectured that a [[graph, undirected graph, nonoriented graph|graph]] is ''[[perfect graph|perfect]]'' iff | ||
none of its induced subgraphs is a <math>C_{2k+1}</math> or the ''complement'' of such a cycle, <math>k \geq 2</math>. | none of its [[induced (with vertices) subgraph|induced subgraphs]] is a <math>\,C_{2k+1}</math> or the ''[[complement of a graph, complementary graph|complement]]'' of such a [[cycle]], <math>k \geq 2</math>. | ||
This conjecture is well-known as the ''Strong Perfect Graph Conjecture'' and is still open. | This conjecture is well-known as the ''Strong Perfect Graph Conjecture'' and is still open. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 13:26, 12 января 2012
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.