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érenceDate
2012Conference title
21st International Symposium on Mathematical Programming (ISMP 2012)Conference date
2012-08Conference city
BerlinConference country
GermanyMetadata
Show full item recordAuthor(s)
Cornaz, DenisLaboratoire 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
graphsRelated items
Showing items related by title and author.
-
Cornaz, Denis; Meurdesoif, Philippe (2014) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Meurdesoif, Philippe (2010) Article accepté pour publication ou publié
-
Nguyen, Viet Hung; Cornaz, Denis (2013-11-02) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico (2017) Article accepté pour publication ou publié