244
правки
Изменения
Нет описания правки
# Найдите $R(P_4, P_4)$
# Завершите доказательство теоремы Хватала, показав, что $R(T_m, K_n) \ge (n-1)(m-1)+1$
# Покажите, что добавление ребра может сделать совершенный граф несовершенным
# Покажите, что удалине ребра может сделать совершенный граф несовершенным
# Докажите, что любой интервальный граф является хордальным
# Докажите, что дополнение любого интервального графа является графом сравнений
# Приведите пример хордального графа, который не является интервальным
# Докажите, что хордальный граф является интервальным тогда и только тогда, когда его дополнение является графом сравнений (теорема Гилмора-Хоффмана)
# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $|H| = \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)
# Докажите, что если $G$ является реберным графом, то $\chi(G) \in \{\omega(G), \omega(G)+1\}$.
# Опишите графы, у которых реберный граф является совершенным
# Докажите, что граф $G$ является совершенным тогда и только тогда, когда его любой непустой индуцированный подграф $H$ содержит независимое множество $A$, такое что $\omega(H \setminus A) < \omega(H)$.
# Рассмотрим граф $G$, такой что для любого индуцированного подграфа $H$ любая максимальная клика и любое максимальное независимое множество имеют общую вершину. Докажите, что $G$ совершенный.
# Докажите, что $G$ обладает свойством из предыдущего задания тогда и только тогда, когда $G$ не содержит индуцированного пути из трех вершин (любые три вершины соединены либо 0, либо 1, либо 3 ребрами).
# Рассмотрим совершенный граф $G$. Докажите, что можно покрыть все вершины графа независимыми множествами (обозначим семейство этих независимых множеств $\mathbb{I}$), а также покрыть все вершины графа кликами (обозначим семейство этих клик как $\mathbb{J}$, что для любых $A \in \mathbb{I}$ и $B \in \mathbb{J}$ выполнено $A \cap B \ne \emptyset$.
# Рассмотрим совершенный граф $G$. Заметим каждую его вершину $x$ на произвольный совершенный граф $G_x$ (вершины графов $G_x$ и $G_y$ соединены друг с другом, если было ребро $xy$). Докажите, что получившийся граф является совершенным.
# Предложите полиномиальный алгоритм проверки, что граф является хордальным.
# Предложите полиномиальный алгоритм поиска $\alpha(G)$ для хордального графа $G$.
# Предложите полиномиальный алгоритм поиска $\chiG)$ для хордального графа $G$.
