Nonrepetitive Colorings of GraphsA Survey
A vertex coloring f of a graph G is nonrepetitive if there are no integer r≥1 and a simple path v1,…,v2r in G such that f(vi)=f(vr+i) for all i=1,…,r. This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveys problems and results on this topic.
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2007-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2007/74639 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A vertex coloring f of a graph G is nonrepetitive if there are no
integer r≥1 and a simple path v1,…,v2r in G such that f(vi)=f(vr+i) for all i=1,…,r. This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveys
problems and results on this topic. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |