Groupe d’études et de recherche en analyse des décisions

G-96-25

Fractional and Integral Colourings

et

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