Fractional and integral colourings

Fractional and integral colourings

0.00 Avg rating0 Votes
Article ID: iaor1998345
Country: Netherlands
Volume: 76
Issue: 2
Start Page Number: 333
End Page Number: 347
Publication Date: Feb 1997
Journal: Mathematical Programming
Authors: ,
Keywords: programming: integer
Abstract:

Let G = (V, E) be an undirected graph and c any vector in ℤ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 χ(Gc) — ⌈η(Gc)⌉ ⩽ 1. We show that for the class of graphs satisfying χ(Gc) = ⌈η(Gc)⌉ (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 χ(Gc) = ⌈η(Gc)⌉ for series-parallel graphs and χ(Gc) ⩽ ⌈η(Gc)⌉ + 1 for graphs that do not have the 4-wheel as a minor.

Reviews

Required fields are marked *. Your email address will not be published.