Просмотр исходного текста страницы Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree

[[Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graph-with-degree]]



<latex>
Добавим условие на связность графа, чтобы убрать тривиальные случаи d = 0, d = 1.

Если d = 2, то G - либо четный цикл, либо дерево, либо нечетный цикл.
Нечетный цикл отпадает по условию, дерево и четный можно раскрасить 2 цветами.

\vspace{3mm}
{\bf Пусть}  d \geq 3:



{\bf Докажем}, что если в графе есть вершина u, со степенью < d, его можно покрасить в d цветов.

Построим обход этого граф в ширину из u.
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.

\vspace{3mm}

{\bf Пусть} теперь все вершины в графе имеют степень d.

Рассмотрим вершины b, c смежные с a.
Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d.

Пусть теперь удаление b, c оставляет граф связным, тогда склеим b и c в вершину d и докажем что G можно раскрасить в d цветов.

Теперь у a степень d - 1 - значит граф со склееными вершинами можно покрасить в d цветов.

Теперь в исходном графе покрасим b, c в цвет d.

Значит G можно покрасить в d цветов.

<\latex>

[[Категория:Решения]]