A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs

A dynamic colouring of a graph is a proper colouring in which no neighbourhood of a non leaf vertex is monochromatic. The dynamic colouring number chi(2)(G) of a graph G is the least number of colours needed for a dynamic colouring of G. Montgomery conjectured that chi(2)(G) <= chi(G) + 2 for all regular graphs G, which would significantly improve the best current upper bound chi(2)(G) <= 2 chi (G). In this note, however, we show that this last upper bound is sharp by constructing, for every integer n >= 2, a regular graph G with chi(G) = n but chi(2)(G) = 2n. In particular, this disproves Montgomery's conjecture. (C) 2017 Elsevier B.V. All rights reserved.