Name
Abstract | ||
|---|---|---|
A vertex colouring of a graph G is nonrepetitive if for any path P=(v"1,v"2,...,v"2"r) in G, the first half is coloured differently from the second half. The Thue choice number of G is the least integer @? such that for every @?-list assignment L of G, there exists a nonrepetitive L-colouring of G. We prove that for any positive integer @?, there is a tree T with @p"c"h(T)@?. On the other hand, it is proved that if G^' is a graph of maximum degree @D, and G is obtained from G^' by attaching to each vertex v of G^' a connected graph of tree-depth at most z rooted at v, then @p"c"h(G)@?c(@D,z) for some constant c(@D,d) depending only on @D and z. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.dam.2011.07.017 | Discrete Applied Mathematics |
Keywords | Field | DocType |
constant c,maximum degree,positive integer,list assignment l,thue choice number,vertex colouring,connected graph,graph g,thue choosability,nonrepetitive l-colouring,vertex v,tree | Integer,Graph,Discrete mathematics,Combinatorics,Existential quantification,Vertex (geometry),Choice number,Degree (graph theory),Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
159 | 17 | 0166-218X |
Citations | PageRank | References |
11 | 0.65 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Francesca Fiorenzi | 1 | 57 | 9.00 |
| Pascal Ochem | 2 | 258 | 36.91 |
| Patrice Ossona de Mendez | 3 | 675 | 47.97 |
| Xuding Zhu | 4 | 1883 | 190.19 |