Nonrepetitive Graph Coloring
Jarosław Grytczuk · Birkhäuser Basel eBooks · 2006
A coloring of the vertices of a graph G is nonrepetitive if no simple path in G looks like a 1 a 2 ... a n a 1 a 2 ... a n. The minimum number of colors needed for a graph G is denoted by π(G). For instance, by the famous 1906 theorem of Thue, π(G) = 3 if G is a simple path with at least 4 vertices. This implies that π(G) ≤ 4 if Δ(G) ≤ 2. But how large can π(G) be for cubic graphs, κ-trees, or planar graphs? This paper is a small survey of problems and results of the above type.