On the facial Thue choice number of plane graphs via entropy compression method
| Autor: | Jens Schreyer, Jakub Przybyło, Erika Fecková Škrabul’áková |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) 010102 general mathematics Entropy compression 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Planar graph Choice number Combinatorics symbols.namesake List size 010201 computation theory & mathematics Computer Science::Discrete Mathematics symbols FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) 0101 mathematics Absolute constant Mathematics 05C10 |
| DOI: | 10.48550/arxiv.1308.5128 |
| Popis: | Let G be a plane graph. A vertex-colouring $$\varphi $$? of G is called facial non-repetitive if for no sequence $$r_1 r_2 \ldots r_{2n}$$r1r2?r2n, $$n\ge 1$$n?1, of consecutive vertex colours of any facial path it holds $$r_i=r_{n+i}$$ri=rn+i for all $$i=1,2,\ldots ,n$$i=1,2,?,n. A plane graph G is facial non-repetitivelyk-choosable if for every list assignment $$L:V\rightarrow 2^{\mathbb {N}}$$L:V?2N with minimum list size at least k there is a facial non-repetitive vertex-colouring $$\varphi $$? with colours from the associated lists. The facial Thue choice number, $$\pi _{fl}(G)$$?fl(G), of a plane graph G is the minimum number k such that G is facial non-repetitively k-choosable. We use the so-called entropy compression method to show that $$\pi _{fl} (G)\le c \varDelta $$?fl(G)≤cΔ for some absolute constant c and G a plane graph with maximum degree $$\varDelta $$Δ. Moreover, we give some better (constant) upper bounds on $$\pi _{fl} (G)$$?fl(G) for special classes of plane graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|