## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 1375-1380 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 8 |

DOIs | |

State | Published - Apr 28 2008 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Keywords

- Graph coloring
- Random graph
- Rhythm threshold
- Thue sequence