Notes on nonrepetitive graph colouring

MaRDI QIDQ1010826zbMATH OpenFDO

Authors János Barát, David R. Wood

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0509608, https://eudml.org/doc/129978, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r99.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A vertex colouring of a graph is emph{nonrepetitive on paths} if there is no path $v_1,v_2,\mathrm{...},v_{2t}$ such that v_i and v_{t+i} receive the same colour for all i=1,2,...,t. We determine the maximum density of a graph that admits a k-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree $Delta$ has a $f(Delta)$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth k and maximum degree $Delta$ has a $O(kDelta)$-colouring that is nonrepetitive on paths, and a $O(kDelt{a}^3)$-colouring that is nonrepetitive on walks.

Recommendations

• Nonrepetitive graph colouring
• Nonrepetitive colorings of graphs -- a survey
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colouring via entropy compression
• Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours

Cited in

(25)

• Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor
• Non-repetitive 3-coloring of subdivided graphs
• Characterisations and examples of graph classes with bounded expansion
• Product structure of graph classes with bounded treewidth
• Nonrepetitive graph colouring
• Nonrepetitive colorings of lexicographic product of graphs
• New bounds for facial nonrepetitive colouring
• Which graphs allow infinite nonrepetitive walks?
• Nonrepetitive colorings of graphs of bounded tree-width
• The complexity of nonrepetitive coloring
• On tree-partition-width
• scientific article; zbMATH DE number 5130733 (Why is no real title available?)
• Anagram-Free Colorings of Graph Subdivisions
• Nonrepetitive colouring via entropy compression
• Breaking the rhythm on graphs
• Nonrepetitive colorings of graphs -- a survey
• Nonrepetitive list colorings of the integers
• Another approach to non-repetitive colorings of graphs of bounded degree
• Tree-partitions with bounded degree trees
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
• On nonrepetitive colorings of paths and cycles
• Restricted coloring problems on graphs with few \(P_4\)'s
• A note about online nonrepetitive coloring \(k\)-trees
• Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
• A note on the thue chromatic number of lexicographic products of graphs

This page was built for publication: Notes on nonrepetitive graph colouring

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