This preprint was accepted November 12, 2007
ABSTRACT:
Назовем подразбиением полного графа $K_n$ любой граф, который можно
получить заменой нескольких ребер $K_n$ на цепочки длины 2 (с каждой
такой цепочкой добавляется новая вершина степени 2).
Пусть $G$ --- связный простой граф с максимальной степенью вершин
$d\ge 86$. В работе доказывается, что динамическая правильная
раскраска вершин графа $G$ в $d$ цветов существует тогда и только
тогда, когда $G$ отличен от $K_{d+1}$ и его подразбиений.
[Full text:
(.ps.gz)]