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

Metadatos

Licencia de uso del documento

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]

Idioma

Communication dans un congrès

Este ítem está publicado en

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

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

semi-definite programming

Theta number

Metadatos

Compartir este ítem

Licencia de uso del documento

How unique is Lovász's theta function?

Idioma

Este ítem está publicado en

Resumen en inglés

Palabras clave en inglés

URI

Orígen

Centros de investigación