Berge's conjecture: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Berge's conjecture''' --- гипотеза Бержа. In 1960, C.Berge conjectured that a graph is ''perfect'' iff none of its induced subgraphs is a <math>C_{…»)
 
Нет описания правки
 
Строка 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.

Навигация