244
правки
Изменения
Нет описания правки
# Приведите пример хордального графа, который не является интервальным
# Докажите, что хордальный граф является интервальным тогда и только тогда, когда его дополнение является графом сравнений (теорема Гилмора-Хоффмана)
# Докажите, что граф $G$ является совершенным тогда и только тогда, когда $|H| = \le \alpha(H)\omega(H)$ для любого $H$ - индуцированного подграфа $G$ (теорема Ловаса)
# Докажите, что если $G$ является реберным графом, то $\chi(G) \in \{\omega(G), \omega(G)+1\}$.
# Опишите графы, у которых реберный граф является совершенным
