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.
Published May 1996 , 23 pages