Geodesic
Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
The electronic journal of combinatorics, Tome 20 (2013) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A vertex colouring of a graph is nonrepetitive if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The nonrepetitive chromatic number of a graph $G$ is the minimum integer $k$ such that $G$ has a nonrepetitive $k$-colouring. Whether planar graphs have bounded nonrepetitive chromatic number is one of the most important open problems in the field. Despite this, the best known upper bound is $O(\sqrt{n})$ for $n$-vertex planar graphs. We prove a $O(\log n)$ upper bound.
DOI : 10.37236/3153
Classification : 05C15, 05C10
Mots-clés : nonrepetitive graph colouring

Vida Dujmović    ; Fabrizio Frati    ; Gwenaël Joret    ; David R. Wood  1

1 Monash University 
@article{10_37236_3153,
     author = {Vida Dujmovi\'c and Fabrizio Frati and Gwena\"el Joret and David R. Wood},
     title = {Nonrepetitive colourings of planar graphs with {\(O(\log} n)\) colours},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {1},
     doi = {10.37236/3153},
     zbl = {1266.05029},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3153/}
}
TY  - JOUR
AU  - Vida Dujmović
AU  - Fabrizio Frati
AU  - Gwenaël Joret
AU  - David R. Wood
TI  - Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3153/
DO  - 10.37236/3153
ID  - 10_37236_3153
ER  - 
%0 Journal Article
%A Vida Dujmović
%A Fabrizio Frati
%A Gwenaël Joret
%A David R. Wood
%T Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3153/
%R 10.37236/3153
%F 10_37236_3153
Vida Dujmović; Fabrizio Frati; Gwenaël Joret; David R. Wood. Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/3153

Cité par Sources :