The Thue choice number versus the Thue chromatic number of graphs

preprint2015arXivOpen access

Abstract

We say that a vertex colouring φφ of a graph GG is nonrepetitive if there is no positive integer nn and a path on 2n2n vertices v1…v2nv_{1}\ldots v_{2n} in GG such that the associated sequence of colours φ(v1)…φ(v2n)φ(v_{1})\ldotsφ(v_{2n}) satisfy φ(vi)=φ(vi+n)φ(v_{i})=φ(v_{i+n}) for all i=1,2,…,ni=1,2,\dots,n. The minimum number of colours in a nonrepetitive vertex colouring of GG is the Thue chromatic number π(G)π(G). For the case of vertex list colourings the Thue choice number πl(G)π_{l}(G) of GG denotes the smallest integer kk such that for every list assignment L:V(G)→2NL:V(G)\rightarrow 2^{\mathbb{N}} with minimum list length at least kk, there is a nonrepetitive vertex colouring of GG 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.