An analog of Brooks' theorem for dynamic colorings (Q509086)

The classical theorem of \textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] characterizes graphs \(G\) whose vertices can be colored by \(\Delta(G)\) colors so that adjacent vertices are colored by distinct colors, where \(\Delta(G)\) denotes the maximum degree. A (vertex) coloring of a graph is called dynamic if adjacent vertices are colored by distinct colors and for each vertex of degree at least two, the set of its neighbors is not monochromatic. This concept is a strengthening of the usual proper coloring of graphs. This paper characterizes graphs that admits a dynamic coloring with at most \(d\) colors when \(\Delta(G)\leq d\) and \(d\geq 6\). Namely, for \(d\geq 6\), a graph of maximum degree at most \(d\) admits a dynamic coloring with at most \(d\) colors if and only if no component is isomorphic to a graph obtained from \(K_{d}\) by subdividing some (or no) edges once. This improves the previous result of the author for \(d\geq 8\) [J. Math. Sci., New York 179, No. 5, 601--615 (2011); translation from Zap. Nauchn. Semin. POMI 381, 47--77 (2010; Zbl 1402.05070)].