| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4650595 | Discrete Mathematics | 2008 | 6 Pages |
We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs FF, if there are absolute constants t,kt,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of FF, denoted by t(F)t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2(d+1)/2 and d+1d+1. We give several general conditions for finiteness of t(F)t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.
