"Записки научных семинаров ПОМИ"

Том 381, стр. 47-77

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

dvk@pdmi.ras.ru

Аннотация: Назовем подразбиением полного графа $K_n$ любой граф, который можно получить заменой нескольких ребер $K_n$ на цепочки длины 2 (с каждой такой цепочкой добавляется новая вершина степени 2). Пусть $G$ -- связный простой граф с максимальной степенью вершин $d\ge 8$. В работе доказывается, что динамическая правильная раскраска вершин графа $G$ в $d$ цветов существует тогда и только тогда, когда $G$ отличен от $K_{d+1}$ и его подразбиений. Библ. -- 7 назв.
Ключевые слова: правильная раскраска, динамическая раскраска, теорема Брукса [proper coloring, dynamic coloring, Brooks' theorem]