On the facial Thue choice number of plane graphs via entropy compression method

Abstract

Let $G$ be a plane graph. A vertex-colouring $\phi$ of $G$ is called {\em facial non-repetitive} if for no sequence $r_1{r}_2\dots r_{2n}$, $n\ge 1$, of consecutive vertex colours of any facial path it holds $r_i=r_{n+i}$ for all $i=1,2,\dots ,n$. A plane graph $G$ is {\em facial non-repetitively $l$-choosable} if for every list assignment $L:V\rightarrow 2\sp{\mathbb{N}}$ with minimum list size at least $l$ there is a facial non-repetitive vertex-colouring $\phi$ with colours from the associated lists. The {\em facial Thue choice number}, ${\pi }_{fl}(G)$, of a plane graph $G$ is the minimum number $l$ such that $G$ is facial non-repetitively $l$-choosable. %In this article we We use the so-called entropy compression method to show that ${\pi }_{fl}(G)\le c\Delta$ for some absolute constant $c$ and $G$ a plane graph with maximum degree $\Delta$. Moreover, we give some better (constant) upper bounds on ${\pi }_{fl}(G)$ for special classes of plane graphs.

References in corpus (2)

• Nonrepetitive Colouring via Entropy Compression
• On the facial Thue choice index via entropy compression

Cited by in corpus (2)

• Nonrepetitive Colouring via Entropy Compression
• The Thue choice number versus the Thue chromatic number of graphs