Show simple item record

dc.contributor.authorZwols, Yori
dc.contributor.authorRies, Bernard
dc.contributor.authorChudnovsky, Maria
dc.date.accessioned2012-05-23T14:35:57Z
dc.date.available2012-05-23T14:35:57Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9279
dc.language.isoenen
dc.subjectStructural graph theoryen
dc.subjectWireless networkingen
dc.subjectStronglyperfectgraphsen
dc.subjectForbidden induced subgraphsen
dc.subjectClaw-freegraphsen
dc.subject.ddc511en
dc.titleClaw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part II. Nontrivial strip-structuresen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherSchool of Computer Science, McGill University;Canada
dc.contributor.editoruniversityotherDepartment of Industrial Engineering and Operations Research, Columbia University;États-Unis
dc.description.abstractenStronglyperfectgraphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-freegraphs that are fractionally stronglyperfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-freegraphs that are fractionally stronglyperfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of stronglyperfectclaw-freegraphs. As a corollary of the results in this paper, we obtain a characterization of claw-freegraphs whose complements are stronglyperfect.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol159en
dc.relation.isversionofjnlissue17en
dc.relation.isversionofjnldate2011
dc.relation.isversionofjnlpages1996-2029en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2011.06.031en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen


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