Fiche du document
8 décembre 2014
- handle: 10670/1.71oc35
- hal: hal-01095638
http://creativecommons.org/licenses/by-nc-nd/ , info:eu-repo/semantics/OpenAccess
Mots-clés
semi-definite programming Theta numberSujets proches
Hours (Time) Natural science Sciences Science of scienceCiter ce document
Arnaud Pêcher et al., « How unique is Lovász's theta function? », HAL-SHS : sciences de l'information, de la communication et des bibliothèques, ID : 10670/1.71oc35
Métriques
Partage / Export
Résumé
The famous Lovász's ϑ function is computable in polynomial time for every graph, as a semi-definite program (Grötschel, Lovász and Schrijver, 1981). The chromatic number and the clique number of every perfect graph G are computable in polynomial time. Despite numerous efforts since the last three decades, stimulated by the Strong Perfect Graph Theo-rem (Chudnovsky, Robertson, Seymour and Thomas, 2006), no combinatorial proof of this result is known. In this work, we try to understand why the "key properties" of Lovász's ϑ function make it so "unique". We introduce an infinite set of convex functions, which includes the clique number ω and ϑ . This set includes a sequence of linear programs which are monotone increasing and converging to ϑ . We provide some evidences that ϑ is the unique function in this setting allowing to compute the chromatic number of perfect graphs in polynomial time.