✦ LIBER ✦

The circular chromatic number of series-parallel graphs with large girth

✍ Scribed by Chien, Chihyun; Zhu, Xuding

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 213 KB
Volume: 33
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200004)33:4<185::aid-jgt1>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1).

📜 SIMILAR VOLUMES

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs

✍ Hell, Pavol; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB 👁 2 views

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 seriesparallel graph G contains a triangle, then both the chromati

The round-up property of the fractional

The round-up property of the fractional chromatic number for proper circular arc graphs

✍ Niessen, Thomas; Kind, Jaakob 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

Let G = (V, E) be a graph and let k be a nonnegative integer. A vector c ∈ Z V + is called k-colorable iff there exists a coloring of G with k colors that assigns exactly c(v) colors to vertex v ∈ V . Denote by χ(G) and χ f (G) the chromatic number and fractional chromatic number, respectively. We p