Thumbnail - Request a copy

Strengthening Lovász bound for coloring with a new graph transformation

Cornaz, Denis; Meurdesoif, Philippe (2012), Strengthening Lovász bound for coloring with a new graph transformation, 21st International Symposium on Mathematical Programming (ISMP 2012), 2012-08, Berlin, Germany

Type
Communication / Conférence
Date
2012
Conference title
21st International Symposium on Mathematical Programming (ISMP 2012)
Conference date
2012-08
Conference city
Berlin
Conference country
Germany
Metadata
Show full item record
Author(s)
Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Meurdesoif, Philippe
Abstract (EN)
Let α(G) and χ(G) denote the stability number and the clique-partition number of G, respectively. Using a new graph transformation, one constructs a new operator Φ which associates to any graph parameter β such that α(G) ≤ β(G) ≤ χ(G) for all graphs G, a graph parameter Φβ such that α(G) ≤ Φβ(G) ≤ χ(G) for all graphs G. We prove that ϑ(G) ≤ Φϑ(G) and that Φχf(G) ≤ χf(G) for all graphs~G, where ϑ is Lovász theta function and χf is the fractional clique-partition number. Φϑ-ϑ is unbounded and numerical experiments show that Φϑ is a significant better lower bound for χ than ϑ.
Subjects / Keywords
graphs