2017/02/03 by Nathan Bowler, Bowler, Nathan, Joshua Erde +10
Computer Science · Neuroscience · #Graph Labeling and Dimension Problems #Nuclear Receptors and Signaling #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1702.00973
A \dynamic colouring of a graph is a proper colouring in which no\nneighbourhood of a non-leaf vertex is monochromatic. The \dynamic\ncolouring number \χ2(G) of a graph G is the least number of colours\nneeded for a dynamic colouring of G.\n Montgomery conjectured that \χ2(G) \≤ \χ(G) + 2 for all regular\ngraphs G, which would significantly improve the best current upper bound\n\χ2(G) \≤ 2\χ(G). In this note, however, we show that this last upper\nbound is sharp by constructing, for every integer n \≥ 2, a regular graph\nG with \χ(G) = n but \χ2(G) = 2n. In particular, this disproves\nMontgomery's conjecture.\n