Steklov Institute of Mathematics at St.Petersburg

PREPRINT 06/2015

AN ANALOG OF BROOKS THEOREM FOR DYNAMIC COLORINGS

This preprint was accepted December 23, 2015

ABSTRACT:
 Let a subdivision of the complete graph   $K_n$ be any graph, which can be 
constructed from $K_n$ by substituting some edges of $K_n$ with chains of two edges 
(every such chain adds to a graph a new vertex of degree 2).

Let $d\ge 6$ and $G$ be a connected graph different from $K_{d+1}$ and its subdivisions
with maximal vertex degree at most $d$. We prove that there is a proper dynamic vertex coloring of $G$ with $d$ colors.

 

Д. В. КАРПОВ

АНАЛОГ ТЕОРЕМЫ БРУКСА ДЛЯ ДИНАМИЧЕСКИХ РАСКРАСОК

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

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