Dynamic proper colorings of a graph

A subdivision of complete graph Kn is any graph that can be obtained from Kn by replacing edges of Kn by chains of two edges (every such chain adds to the graph a new vertex of degree 2). Let G be a connected graph with maximal vertex degree d, d ≥ 8. We prove that there is a proper dynamic vertex coloring of G with d colors iff G is distinct from Kd+1 and its subdivisions. Bibliography: 7 titles. © 2011 Springer Science+Business Media, Inc.