Show simple item record

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.accessioned2010-11-09T15:10:11Z
dc.date.available2010-11-09T15:10:11Z
dc.date.issued2010
dc.identifier.issn1571-0653
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5025
dc.language.isoenen
dc.subjectLovász theta function
dc.subjectauxiliary line graph
dc.subjectGraph coloring
dc.subject.ddc511en
dc.titleThe sandwich line-graph
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité Bordeaux 1;France
dc.description.abstractenWe observe that View the MathML source for any graph G with n vertices, where View the MathML source is any acyclic orientation of G and where View the MathML source is the (complement of the) auxiliary line graph introduced in [Cornaz, D., and Jost, V., A one-to-one correspondence between colorings and stable sets, Operations Research Letters 36 (2008), 673–676]. (Where as usual, ω and χ denote the clique number and the chromatic number.) It follows that, for any graph parameter β(G) sandwiched between ω(G) and χ(G), then View the MathML source is sandwiched between ω(G) and χ(G) too. Numerical experiments show that Φtheta is closer to χ than theta, where theta is Lovász theta function
dc.relation.isversionofjnlnameElectronic Notes in Discrete Mathematics
dc.relation.isversionofjnlvol36
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages955-960
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.endm.2010.05.121
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2019-07-01T08:18:33Z
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record