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

Abstract: Let

G

be a plane graph. A vertex-colouring

v a r p h i

of

G

is called {em facial non-repetitive} if for no sequence

r_{1} r_{2} d o t s r_{2 n}

,

n g e q 1

, of consecutive vertex colours of any facial path it holds

r_{i} = r_{n + i}

for all

i = 1, 2, d o t s, n

. A plane graph

G

is {em facial non-repetitively

l

-choosable} if for every list assignment

L : V i g h t a r r o w 2 s p m a t h b b N

with minimum list size at least

l

there is a facial non-repetitive vertex-colouring

v a r p h i

with colours from the associated lists. The {em facial Thue choice number},

p i_{f l} (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

p i_{f l} (G) l e c D e l t a

for some absolute constant

c

and

G

a plane graph with maximum degree

D e l t a

. Moreover, we give some better (constant) upper bounds on

p i_{f l} (G)

for special classes of plane graphs.

Recommendations

Cites Work

Cited In (8)

This page was built for publication: On the facial Thue choice number of plane graphs via entropy compression method