Nonrepetitive colorings of graphs -- a survey
type: Item
instance of: scholarly article
title: Nonrepetitive colorings of graphs -- a survey
zbMATH Open document ID: 1139.05020
DOI: 10.1155/2007/74639
author: Jarosław Grytczuk
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2008-06-03T00:00:00Z
full work available at URL: https://eudml.org/doc/54166
review text: Summary: A vertex coloring \(f\) of a graph \(G\) is nonrepetitive if there are no integer \(r\geq 1\) and a simple path \(\nu_1,\dots,\nu_{2r}\) in \(G\) such that \(f(\nu_i)= f(\nu_{r+i})\) for all \(i=1,\dots,r\). This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveys problems and results on this topic.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5282441
MaRDI profile type: Publication
OpenAlex ID: W1981225002
cites work: Automatic Sequences
cites work: Q3659988
cites work: Q4529547
cites work: Aperiodic words on three symbols.
cites work: Aperiodic words on three symbols. II.
cites work: Q3919722
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Q3682492
cites work: Pattern avoidance: themes and variations
cites work: Thue-like sequences and rainbow arithmetic progressions
cites work: There are ternary circular square-free words of length \(n\) for \(n \geq\) 18
cites work: Nonrepetitive colorings of graphs
cites work: Nonrepetitive colorings of graphs of bounded tree-width
cites work: On square-free vertex colorings of graphs
cites work: Q3424780
cites work: Orderings on graphs and game coloring number
cites work: Tree-depth, subgraph coloring and homomorphism bounds
cites work: Notes on nonrepetitive graph colouring
cites work: Nonrepetitive colorings of trees
cites work: Q4412125
cites work: Breaking the rhythm on graphs
cites work: A 4-Color Theorem for Surfaces of Genus g
cites work: Oriented graph coloring
cites work: On acyclic colorings of planar graphs
cites work: Homomorphisms of edge-colored graphs and Coxeter groups
cites work: Q5475511
cites work: Which graphs allow infinite nonrepetitive walks?
cites work: Non-repetitive colorings of infinite sets
cites work: Avoidable patterns in strings of symbols
cites work: Non-repetitive tilings
cites work: The fixing block method in combinatorics on words
description: scientific article; zbMATH DE number 5282441