Thumbnail - Request a copy

Chromatic Gallai identities operating on Lovász number

Cornaz, Denis; Meurdesoif, Philippe (2014), Chromatic Gallai identities operating on Lovász number, Mathematical Programming, 144, 1-2, p. 347-368. 10.1007/s10107-013-0636-1

Type
Article accepté pour publication ou publié
Date
2014
Journal name
Mathematical Programming
Volume
144
Number
1-2
Publisher
Springer
Pages
347-368
Publication identifier
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)
If G is a triangle-free graph, then two Gallai identities can be written as α(G)+χ−(L(G))=|V(G)|=α(L(G))+χ−(G) , where α and χ− denote the stability number and the clique-partition number, and L(G) is the line graph of G . We show that, surprisingly, both equalities can be preserved for any graph G by deleting the edges of the line graph corresponding to simplicial pairs of adjacent arcs, according to any acyclic orientation of G . As a consequence, one obtains an operator Φ which associates to any graph parameter β such that α(G)≤β(G)≤χ−(G) for all graph G , a graph parameter Φβ such that α(G)≤Φβ(G)≤χ−(G) for all graph G . We prove that ϑ(G)≤Φϑ(G) and that Φχ−f(G)≤χ−f(G) for all graph G , where ϑ is Lovász theta function and χ−f is the fractional clique-partition number. Moreover, χ−f(G)≤Φϑ(G) for triangle-free G . Comparing to the previous strengthenings Ψϑ and ϑ+△ of ϑ , numerical experiments show that Φϑ is a significant better lower bound for χ− than ϑ .
Subjects / Keywords
Gallai identities; Graph coloring; Lovász number; Fractional chromatic number; Semidefinite programming