Breaking the rhythm on graphs Original Research Article

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 image, if there are absolute constants image 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 image, denoted by image. For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between image and image. We give several general conditions for finiteness of image, as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.