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

Abstract

A \emph{dynamic colouring} of a graph is a proper colouring in which no neighbourhood of a non-leaf vertex is monochromatic. The \emph{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)\le \chi (G)+2$ for all regular graphs $G$, which would significantly improve the best current upper bound ${\chi }_2(G)\le 2\chi (G)$. In this note, however, we show that this last upper bound is sharp by constructing, for every integer $n\ge 2$, a regular graph $G$ with $\chi (G)=n$ but ${\chi }_2(G)=2n$. In particular, this disproves Montgomery's conjecture.

4 pages, 1 colour figure