Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650435 | Discrete Mathematics | 2008 | 6 Pages |
Abstract
A sequence of the form s1s2…sms1s2…sms1s2…sms1s2…sm is called a repetition. A vertex-coloring of a graph is called nonrepetitive if none of its paths is repetitively colored. We answer a question of Grytczuk [Thue type problems for graphs, points and numbers, manuscript] by proving that every outerplanar graph has a nonrepetitive 12-coloring. We also show that graphs of tree-width t have nonrepetitive 4t4t-colorings.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
André Kündgen, Michael J. Pelsmajer,