The circular chromatic number of series-parallel graphs

By P. Hell, Xuding Zhu. Journal of Graph Theory, 2000

78 citations recorded by the source corpus.

In this article, we consider the circular chromatic number χc(G) of series-parallel graphs G. It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series-parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series-parallel graph G has girth at least 2 ⌊(3k - 1)-2⌋, then χc(G) ≤ 4k-(2k - 1). The special case k = 2 of this result implies that a triangle free series-parallel graph G has circular chromatic number at most 8-3. Therefore, the circular chromatic number of a series-parallel graph (and of a K4-minor free graph) is either 3 or at most 8-3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K5-minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000

View Paper: https://www.semanticscholar.org/paper/d7db61e62b6996d480b9de31bb77d42e5485b669