Back

G-96-25

Fractional and Integral Colourings

and

BibTeX reference

Let G = (V,E) be an undirected graph and c any vector in Z+V(G). Denote by (Gc) (resp. (Gc)) the chromatic number (resp. fractional chromatic number) of G with respect to c. We study graphs for which We show that for the class of graphs satisfying (a class generalizing perfect graphs), an analogue of the Duplication Lemma does not hold. We also describe a 2-vertex cut decomposition procedure related to the integer decomposition property. We use this procedure to show that for series-parallel graphs and for graphs that do not have the 4-wheel as a minor.

, 23 pages

Research Axis