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.

Review text

Summary: A vertex colouring of a graph is nonrepetitive on paths if there is no path \(v_1,v_2,\dots,v_{2t}\) such that \(v_i\) and \(v_{t+i}\) receive the same colour for all \(i=1,2,\dots,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(k\Delta)\)-colouring that is nonrepetitive on paths, and a \(O(k\Delta^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

(29)

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

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)