Afficher la notice abrégée

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorPÊCHER, Arnaud
hal.structure.identifierResearch Group on Graph Theory and Combinatorics [Barcelona]
dc.contributor.authorSERRA, Oriol
hal.structure.identifierLaboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]
dc.contributor.authorWAGLER, Annegret K.
hal.structure.identifierDepartment of Mathematics [Hangzhou]
dc.contributor.authorZHU, Xuding
dc.date.accessioned2024-04-04T03:19:50Z
dc.date.available2024-04-04T03:19:50Z
dc.date.created2014-12-08
dc.date.issued2014-12-08
dc.date.conference2014-12-08
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194543
dc.description.abstractEnThe 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.
dc.language.isoen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/
dc.subject.ensemi-definite programming
dc.subject.enTheta number
dc.title.enHow unique is Lovász's theta function?
dc.typeCommunication dans un congrès
dc.subject.halSciences de l'Homme et Société/Sciences de l'information et de la communication
dc.subject.halInformatique [cs]/Mathématique discrète [cs.DM]
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleVIII ALIO/EURO Workshop on Applied Combinatorial Optimization
bordeaux.countryUY
bordeaux.conference.cityMontevideo
bordeaux.peerReviewedoui
hal.identifierhal-01095638
hal.version1
hal.invitednon
hal.proceedingsnon
hal.conference.end2014-12-10
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01095638v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2014-12-08&rft.au=P%C3%8ACHER,%20Arnaud&SERRA,%20Oriol&WAGLER,%20Annegret%20K.&ZHU,%20Xuding&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée