Оглавление
Сильная теорема о совершенном графе
-
Определение и доказательство сильной теоремы о совершенном графе
- Сильная теорема о совершенном графе запрещает наличие нечетных отверстий и нечетных анти-отверстий в совершенных графах.
- Доказательство теоремы было анонсировано в 2002 году и опубликовано в 2006 году, авторы получили премию в размере 10 000 долларов и премию Фулкерсона.
- Совершенный граф характеризуется равенством числа клик и хроматического числа для каждого индуцированного подграфа.
-
Гипотеза и доказательство Берже
- Клод Берже предположил, что каждый граф Берже совершенен, что эквивалентно сильной теореме о совершенном графе.
- Гипотеза о сильном совершенном графе была доказана в 2002 году, а затем переименована в теорему о сильном совершенном графе.
-
Связь с теоремой о слабом совершенном графе
- Теорема о слабом совершенном графе, доказанная в 1972 году, утверждает, что дополнение к каждому совершенному графу также является совершенным.
- Сильная теорема о совершенном графе следует из теоремы о слабом совершенном графе, так как характеристика запрещенного графа является самодополняющей.
-
Доказательство Чудновского и др.
- Доказательство следует схеме, предложенной в 2001 году, и основано на структурных разложениях графов.
- Минимально несовершенный граф Берге не может иметь ни одного из пяти основных классов совершенных графов или четырех типов структурных декомпозиций, что исключает существование контрпримера к теореме.
- Четыре типа структурных декомпозиций включают 2-соединения, дополнения к 2-соединениям, сбалансированные косые разбиения и однородные пары.
- Анализ конкретных случаев позволяет доказать, что каждый граф Берге относится к одному из базовых классов или имеет один из типов структурных декомпозиций.
Полный текст статьи: