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

الأصل · EN

Let G be a plane graph. A vertex-colouring φ of G is called facial non-repetitive if for no sequence r₁ r₂ r₂ₙ, n≥ 1, of consecutive vertex colours of any facial path it holds rᵢ=rₙ₊ᵢ for all i=1,2,,n. A plane graph G is facial non-repetitively l-choosable if for every list assignment L:V→ 2N with minimum list size at least l there is a facial non-repetitive vertex-colouring φ with colours from the associated lists. The 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.