کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650595 | 1342494 | 2008 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Breaking the rhythm on graphs Breaking the rhythm on graphs](/preview/png/4650595.png)
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.
Journal: Discrete Mathematics - Volume 308, Issue 8, 28 April 2008, Pages 1375–1380