PÊCHER, Arnaud; SERRA, Oriol; WAGLER, Annegret K.; ZHU, Xuding

Métadonnées

Licence d’utilisation du document

http://creativecommons.org/licenses/by-nc-nd/

PÊCHER, Arnaud
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]

SERRA, Oriol
Research Group on Graph Theory and Combinatorics [Barcelona]

WAGLER, Annegret K.
Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]

Langue

Communication dans un congrès

Ce document a été publié dans

VIII ALIO/EURO Workshop on Applied Combinatorial Optimization, 2014-12-08, Montevideo. 2014-12-08

Résumé en anglais

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.< Réduire

Mots clés en anglais

semi-definite programming

Theta number

Métadonnées

Partager cette publication !

Licence d’utilisation du document

How unique is Lovász's theta function?

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

Origine

Unités de recherche