Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree

Материал из DISCOPAL
< Участник:Kirillskor
Версия от 19:55, 9 декабря 2017; Kirillskor (обсуждение | вклад) (Новая страница: «Добавим условие на связность графа, чтобы убрать тривиальные случаи d = 0, d = 1. Если d = 2, то…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Если d = 2, то G - либо четный цикл, либо дерево, либо нечетный цикл.

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

Пусть d >= 3:

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

Построим обход этого граф в ширину из u.

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

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