| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Nonrepetitive colorings of graphs
Abstract : 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.
Cited literature [5 references]
https://hal.inria.fr/hal-01184372
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:05 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:02:56 AM
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:05 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:02:56 AM
File
dmAE0126.pdf
Publisher files allowed on an open archive