Nonrepetitive Colorings of Graphs

Noga Alon, Jarosław Grytczuk, Mariusz Hałuszczak, Oliver Riordan

Research output: Contribution to journalArticle

85 Scopus citations

Abstract

A sequence a = a1a2 ... an is said to be nonrepetitive if no two adjacent blocks of a are exactly the same. For instance, the sequence 1232321 contains a repetition 2323, while 123132123213 is nonrepetitive. A theorem of Thue asserts that, using only three symbols, one can produce arbitrarily long nonrepetitive sequences. In this paper we consider a natural generalization of Thue's sequences for colorings of graphs. A coloring of the set of edges of a given graph G is nonrepetitive if the sequence of colors on any path in G is nonrepetitive. We call the minimal number of colors needed for such a coloring the Thue number of G and denote it by π(G). The main problem we consider is the relation between the numbers π(G) and δ(G). We show, by an application of the Lovász Local Lemma, that the Thue number stays bounded for graphs with bounded maximum degree, in particular, π(G) ≤ cδ(G)2 for some absolute constant c. For certain special classes of graphs we obtain linear upper bounds on π(G), by giving explicit colorings. For instance, the Thue number of the complete graph Kn is at most 2n - 3, and π(T) ≤ 4(δ(T) - 1) for any tree T with at least two edges. We conclude by discussing some generalizations and proposing several problems and conjectures.

Original languageEnglish (US)
Pages (from-to)336-346
Number of pages11
JournalRandom Structures and Algorithms
Volume21
Issue number3-4
DOIs
StatePublished - Jan 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Graph colorings
  • Nonrepetitive sequences

Fingerprint Dive into the research topics of 'Nonrepetitive Colorings of Graphs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Grytczuk, J., Hałuszczak, M., & Riordan, O. (2002). Nonrepetitive Colorings of Graphs. Random Structures and Algorithms, 21(3-4), 336-346. https://doi.org/10.1002/rsa.10057