Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours

Details Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours

2012-02-08

arxiv.org/abs/1202.1569v2

Mathematics

Combinatorics

Scientific paper

A vertex colouring of a graph is \emph{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 \emph{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.

Affiliated with

Also associated with

No associations

Rating

Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-63813