The round-up property of the fractional chromatic number for proper circular arc graphs
✍ Scribed by Niessen, Thomas; Kind, Jaakob
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 131 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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 prove that χ(G) = χ f (G) holds for every proper circular arc graph G. For this purpose, a more general round-up property is characterized by means of a polyhedral description of all k-colorable vectors. Both round-up properties are equivalent for proper circular arc graphs. The polyhedral description is established and, as a by-product, a known coloring algorithm is generalized to multicolorings. The round-up properties do not hold for the larger classes of circular arc graphs and circle graphs, unless P = NP .