Pattern avoidance on graphs

DOI10.1016/j.disc.2005.11.071zbMath1149.05016OpenAlexW1981075828MaRDI QIDQ878624

Jarosław Grytczuk

Publication date: 26 April 2007

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

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

zbMATH Keywords

avoidable patternLovász Local Lemmanonrepetitive graph coloringpattern chromatic number

Mathematics Subject Classification ID

Combinatorics on words (68R15) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (12)

Facial anagram-free edge-coloring of plane graphs ⋮ On avoding \(r\)-repetitions in \(\mathbb R^2\) ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ On some interesting ternary formulas ⋮ Pathwidth and nonrepetitive list coloring ⋮ An estimate for the probability of dependent events ⋮ Grasshopper avoidance of patterns ⋮ Facial non-repetitive edge-coloring of plane graphs ⋮ Highly nonrepetitive sequences: Winning strategies from the local lemma ⋮ Nonrepetitive and pattern-free colorings of the plane ⋮ Facial Nonrepetitive Vertex Coloring of Plane Graphs ⋮ A Frameless 2-Coloring of the Plane Lattice

Cites Work

• Growth problems for avoidable words
• Substitution dynamical systems - spectral analysis
• Avoidable patterns in strings of symbols
• Square-free and cube-free colorings of the ordinals
• On nonrepetitive sequences
• Non-repetitive colorings of infinite sets
• Open Problems in Pattern Avoidance
• Nonrepetitive colorings of graphs
• A Characterization of the Morse Minimal Set
• Graph colouring and the probabilistic method
• Multiplicative properties of the Thue-Morse sequence
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pattern avoidance on graphs