Санкт - Петербургское отделение Математического института им. В.А. Стеклова РАН

ПРЕПРИНТ 09/2009

ДИНАМИЧЕСКИЕ ПРАВИЛЬНЫЕ РАСКРАСКИ ВЕРШИН ГРАФА

This preprint was accepted November 25, 2009

АННОТАЦИЯ:
Назовем подразбиением полного графа  $K_n$ любой граф, который можно
получить заменой нескольких ребер $K_n$ на цепочки длины 2 (с каждой
такой цепочкой добавляется новая вершина степени 2).

Пусть $G$ --- связный простой граф с максимальной степенью вершин
$d\ge 8$. В работе доказывается, что динамическая правильная
раскраска вершин графа $G$ в $d$ цветов существует тогда и только
тогда, когда $G$ отличен от  $K_{d+1}$ и его подразбиений.

Ключевые слова:    граф, правильная раскраска, динамическая раскраска, теорема Брукса