31.Задача о раскраске хордальных графов

Вершина называется симплициальной , если её окружение клика.

Лемма. В любом хордальном графе есть симплициальная вершина.

Симплициальное упорядочение.

Если удалить симплициальную вершину, то оставшийся граф хордальный => есть симплициальные вершины... повторяем то же самое пока не дойдём до пустого графа.

Пусть v₁, v₂, ..., v_n - набор симплициальных вершин , которые мы удаляли, G₁, G₂, ..., G_n - набор графов которые мы получали после удаления каждой такой вершины (G₁ = G). v_i - симплициальная вершина в графе Gi, а G_i+1 = G_i - v_i

Утверждение. Для любого графа плотность(w(G))хроматичекого числа

Теорема. Для любого хордального графа хроматическое число равно плотности графа.(графы для которых выполняется это равенство наз-ся совершенными)

Док-во. Пусть w(G) = k. Покажем что G можно раскрасить в k цветов. Будем доказывать это по индукции, последовательно раскрашивая графы G_n, G_n-1,..., G₁. G_n состоит из 1 вершины - красим её в любой цвет от 1 до k. Допустим граф G_i раскрашен не более чем в k цветов. Покажем что вершину x_i можно окрасить в один из этих цветов, сохраняя правильность раскраски. Т.к. x_i - симплициальная вершина графа G_i, то мн-во всех смежных с ней вершин является кликой. Т.к. при добавлении к мн-ву вершин кликки вершины x_i тоже получаем клику, значит вершин смежных с x_i <=k-1.

А значит сущ. цвет не использованный в смежных вершинах. Красим x_i в этот цвет. => исходный граф можно раскрасить в k цветов=> хроматическое число не превосходит плотности графа, а учитывая утверждение мы получили док-во теоремы.