https://hal.inria.fr/hal-01184372Alon, NogaNogaAlonRaymond and Beverly Sackler Faculty of Exact Sciences - Tel Aviv University [Tel Aviv]Grytczuk, JaroslawJaroslawGrytczukFaculty of Mathematics, Computer Science and Econometric [Zielona Góra] - University of Zielona GóraNonrepetitive colorings of graphsHAL CCSD2005nonrepetitive graph coloringThue sequencesplanar graphs[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]Episciences Iam, CoordinationStefan Felsner2015-08-14 11:38:052017-05-11 01:02:532015-08-14 16:39:24enConference papershttps://hal.inria.fr/hal-01184372/document10.46298/dmtcs.3415application/pdf1A 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.