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\ge8$, $G$ is a connected graph with maximal vertex degree $d$. We proof that there is a proper dynamic vertex coloring of $G$ with $d$ colors iff $G$ is distinct from $K_{d+1}$ and its subdivisions. Bibl. 7 titles.
Key words and phrases:proper coloring, dynamic coloring, Brooks' theorem.