Mathematics – Combinatorics
Scientific paper
2005-09-26
Electronic J. Combinatorics 15:R99, 2008
Mathematics
Combinatorics
Scientific paper
A vertex colouring of a graph is \emph{nonrepetitive on paths} if there is no path $v_1,v_2,...,v_{2t}$ such that v_i and v_{t+i} receive the same colour for all i=1,2,...,t. We determine the maximum density of a graph that admits a k-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree $\Delta$ has a $f(\Delta)$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth k and maximum degree $\Delta$ has a $O(k\Delta)$-colouring that is nonrepetitive on paths, and a $O(k\Delta^3)$-colouring that is nonrepetitive on walks.
Barát János
Wood David R.
No associations
LandOfFree
Notes on Nonrepetitive Graph Colouring 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 Notes on Nonrepetitive Graph Colouring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Notes on Nonrepetitive Graph Colouring will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-503649