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

Link:
Autor/in:
Erscheinungsjahr:
2017
Medientyp:
Text
Schlagworte:
  • Dynamic colouring
  • Graph colouring
Beschreibung:
  • 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χ2(G) of a graph G is the least number of colours needed for a dynamic colouring of G. Montgomery conjectured that χ2(G)≤χ(G)+2 for all regular graphs G, which would significantly improve the best current upper bound χ2(G)≤2χ(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 χ(G)=n but χ2(G)=2n. In particular, this disproves Montgomery's conjecture.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/5f71ec0a-d62e-4f62-aea8-c6fb27123d65