2013/08/23 by Przybyło, Jakub, Schreyer, Jens, Škrabuľáková, Erika
#05C10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1308.5128
Let G be a plane graph. A vertex-colouring φ of G is called \em facial non-repetitive if for no sequence r1 r2 … r2n, n≥ 1, of consecutive vertex colours of any facial path it holds ri=rn+i for all i=1,2,…,n. A plane graph G is \em facial non-repetitively l-choosable if for every list assignment L:V→ 2\spℕ with minimum list size at least l there is a facial non-repetitive vertex-colouring φ with colours from the associated lists. The \em facial Thue choice number, π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 πfl (G)≤ c Δ for some absolute constant c and G a plane graph with maximum degree Δ. Moreover, we give some better (constant) upper bounds on πfl (G) for special classes of plane graphs.