The Thue choice number versus the Thue chromatic number of graphs

Abstract

We say that a vertex colouring $\phi$ of a graph $G$ is nonrepetitive if there is no positive integer $n$ and a path on $2n$ vertices $v_1\dots v_{2n}$ in $G$ such that the associated sequence of colours $\phi (v_1)\dots \phi (v_{2n})$ satisfy $\phi (v_i)=\phi (v_{i+n})$ for all $i=1,2,\dots ,n$. The minimum number of colours in a nonrepetitive vertex colouring of $G$ is the Thue chromatic number $\pi (G)$. For the case of vertex list colourings the Thue choice number ${\pi }_l(G)$ of $G$ denotes the smallest integer $k$ such that for every list assignment $L:V(G)\to 2^{\mathbb{N}}$ with minimum list length at least $k$, there is a nonrepetitive vertex colouring of $G$ from the assigned lists. Recently it was proved that the Thue chromatic number and the Thue choice number of the same graph may have an arbitrary large difference in some classes of graphs. Here we give an overview of the known results where we compare these two parameters for several families of graphs and we also give a list of open problems on this topic.

References in corpus (7)

• Nonrepetitive Colouring via Entropy Compression
• Entropy compression method applied to graph colorings
• On the facial Thue choice index via entropy compression
• Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
• On the facial Thue choice number of plane graphs via entropy compression method
• A note on the Thue chromatic number of lexicographic products of graphs
• A note on acyclic vertex-colorings