Institute for Theoretical Information Technology

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

Authors

T. Niessen, J. Kind,

Abstract

        Let G=(V,E) be a graph of order n and let k be a non-negative integer. A n-dimensional non-negative integral vector c is called k-colorable iff there exists a coloring of G with k colors that assigns exactly c(v) colors to every vertex v. G is said to have the simple round-up property if its chromatic number can be obtained by rounding-up its fractional chromatic number. We prove this property for proper circular arc graphs. For this purpose, a more general round-up property is characterized by means of a polyhedral description of the set 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.

BibT_EX Reference Entry 

@article{NiKi00,
	author = {Thomas Niessen and Jaakob Kind},
	title = "The round-up property of the fractional chromatic number for proper circular arc graphs",
	pages = "256-267",
	journal = "Journal of Graph Theory",
	volume = "33",
	year = 2000,
	hsb = RWTH-CONV-223164,
	}

Downloads

 _{Download bibtex-file}

Sorry, this paper is currently not available for download.