Show simple item record

A note on chromatic properties of threshold graphs

dc.contributor.authorZenklusen, Rico*
dc.contributor.authorde Werra, Dominique*
dc.contributor.authorRies, Bernard*
dc.date.accessioned2012-07-13T13:32:36Z
dc.date.available2012-07-13T13:32:36Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9745
dc.language.isoenen
dc.subjectChromishold graphsen
dc.subjectChromatic numberen
dc.subjectStable setsen
dc.subjectThreshold valuesen
dc.subjectThreshold graphen
dc.subject.ddc511en
dc.titleA note on chromatic properties of threshold graphsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Mathematics, Massachusetts Institute of Technology;États-Unis
dc.contributor.editoruniversityotherDépartement de Mathématiques, Ecole Polytechnique Fédérale de Lausanne;Suisse
dc.description.abstractenIn threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer p, when is it possible to find weights (in general depending on p) for the vertices and a threshold value tp such that for any subset S of vertices the sum of the weights is at most tp if and only if S generates a subgraph with chromatic number at most p−1? We show that threshold graphs do have this property and we show that one can even find weights which are valid for all values of p simultaneously.en
dc.relation.isversionofjnlnameDiscrete Mathematics
dc.relation.isversionofjnlvol312en
dc.relation.isversionofjnlissue10en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages1838-1843en
dc.relation.isversionofdoi10.1016/j.disc.2012.01.036en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds452255*
hal.person.labIds408616*
hal.person.labIds989*
hal.identifierhal-01509687*


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