Breaking the rhythm on graphs

DOI10.1016/j.disc.2007.07.063zbMath1135.05018OpenAlexW2043721341MaRDI QIDQ2476277

Noga Alon, Jarosław Grytczuk

Publication date: 18 March 2008

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

Full work available at URL: https://doi.org/10.1016/j.disc.2007.07.063

zbMATH Keywords

graph coloringrandom graphThue sequencerhythm threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items

Nonrepetitive colorings of graphs -- a survey ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Nonrepetitive colouring via entropy compression ⋮ Avoiding Multiple Repetitions in Euclidean Spaces ⋮ Splitting necklaces and measurable colorings of the real line ⋮ Nonrepetitive colorings of graphs

Cites Work

• Nonrepetitive colorings of graphs of bounded tree-width
• Graph minors. V. Excluding a planar graph
• Avoidable patterns in strings of symbols
• Homomorphisms of edge-colored graphs and Coxeter groups
• There are ternary circular square-free words of length \(n\) for \(n \geq\) 18
• On maximal paths and circuits of graphs
• Automatic Sequences
• Nonrepetitive colorings of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item