Premium
The round‐up property of the fractional chromatic number for proper circular arc graphs
Author(s) -
Niessen Thomas,
Kind Jaakob
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200004)33:4<256::aid-jgt7>3.0.co;2-2
Subject(s) - combinatorics , mathematics , chromatic scale , vertex (graph theory) , arc (geometry) , graph , integer (computer science) , discrete mathematics , fractional coloring , graph power , geometry , line graph , computer science , programming language
Let G = ( V, E ) be a graph and let k be a nonnegative integer. A vector c ∈ ℤ 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 . © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 256–267, 2000