Breaking the rhythm on graphs

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 F, if there are absolute constants t, 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 F, denoted by t (F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d + 1)/2 and d + 1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open. (C) 2007 Elsevier B.V. All rights reserved.