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

DOI10.1016/J.DAM.2017.05.004zbMATH Open1367.05068arXiv1702.00973OpenAlexW2602246102WikidataQ123238184 ScholiaQ123238184MaRDI QIDQ2012068FDOQ2012068

Authors: Nathan Bowler, Joshua Erde, Florian Lehner, Martin Merker, Max F. Pitz, Konstantinos S. Stavropoulos 

Publication date: 27 July 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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} $ch{i}_2(G)$ of a graph $G$ is the least number of colours needed for a dynamic colouring of $G$. Montgomery conjectured that $ch{i}_2(G)leqchi(G)+2$ for all regular graphs $G$, which would significantly improve the best current upper bound $ch{i}_2(G)leq2chi(G)$. In this note, however, we show that this last upper bound is sharp by constructing, for every integer $ngeq2$, a regular graph $G$ with $chi(G)=n$ but $ch{i}_2(G)=2n$. In particular, this disproves Montgomery's conjecture.

Full work available at URL: https://arxiv.org/abs/1702.00973

Recommendations

• On \(r\)-dynamic chromatic number of graphs
• Dynamic chromatic number of regular graphs
• scientific article; zbMATH DE number 6383853
• On the dynamic coloring of graphs
• Dynamic chromatic number of bipartite graphs

zbMATH Keywords

graph colouringdynamic colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• On dynamic coloring for planar graphs and graphs of higher genus
• Title not available (Why is that?)
• On the dynamic coloring of graphs
• On the list dynamic coloring of graphs
• On \(r\)-dynamic coloring of grids
• On \(r\)-dynamic coloring of graphs
• Dynamic coloring of graphs having no \(K_5\) minor
• Title not available (Why is that?)
• Dynamic chromatic number of regular graphs
• On \(r\)-dynamic chromatic number of graphs
• On the difference between chromatic number and dynamic chromatic number of graphs
• Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number
• Disjoint independent dominating sets in graphs
• Title not available (Why is that?)
• Coverings by minimal transversals

Cited In (10)

• Independent domination, colorings and the fractional idomatic number of a graph
• List \(r\)-hued chromatic number of graphs with bounded maximum average degrees
• Dynamic chromatic number of regular graphs
• On \(r\)-dynamic chromatic number of graphs
• 3-dynamic coloring of planar triangulations
• More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
• Graph \(r\)-hued colorings -- a survey
• On dynamic coloring of certain cycle-related graphs
• Dynamic list coloring of 1-planar graphs
• Weak dynamic coloring of planar graphs

This page was built for publication: A counterexample to montgomery's conjecture on dynamic colourings of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012068)