Show simple item record

Chromatic Gallai identities operating on Lovász number

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCornaz, Denis*
hal.structure.identifier
dc.contributor.authorMeurdesoif, Philippe*
dc.date.accessioned2013-04-03T12:52:01Z
dc.date.available2013-04-03T12:52:01Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11181
dc.language.isoenen
dc.subjectGallai identitiesen
dc.subjectGraph coloringen
dc.subjectLovász numberen
dc.subjectFractional chromatic numberen
dc.subjectSemidefinite programmingen
dc.subject.ddc005en
dc.titleChromatic Gallai identities operating on Lovász numberen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIf 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 ϑ .en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol144
dc.relation.isversionofjnlissue1-2
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages347-368
dc.relation.isversionofdoi10.1007/s10107-013-0636-1en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01497129*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record