Noga Alon ; Jaroslaw Grytczuk

Nonrepetitive colorings of graphs
dmtcs:3415 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3415
Nonrepetitive colorings of graphsArticle
Authors: Noga Alon ^{1}; Jaroslaw Grytczuk ^{2}
NULL##NULL
Noga Alon;Jaroslaw Grytczuk
1 Raymond and Beverly Sackler Faculty of Exact Sciences [Tel Aviv]
2 Faculty of Mathematics, Computer Science and Econometric [Zielona Góra]
A vertex coloring of a graph $G$ is $k \textit{nonrepetitive}$ if one cannot find a periodic sequence with $k$ blocks on any simple path of $G$. The minimum number of colors needed for such coloring is denoted by $\pi _k(G)$ . This idea combines graph colorings with Thue sequences introduced at the beginning of 20th century. In particular Thue proved that if $G$ is a simple path of any length greater than $4$ then $\pi _2(G)=3$ and $\pi_3(G)=2$. We investigate $\pi_k(G)$ for other classes of graphs. Particularly interesting open problem is to decide if there is, possibly huge, $k$ such that $\pi_k(G)$ is bounded for planar graphs.
János Barát;David R. Wood, 2008, Notes on Nonrepetitive Graph Colouring, The Electronic Journal of Combinatorics, 15, 1, 10.37236/823, https://doi.org/10.37236/823.