Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part II. Nontrivial strip-structures
Zwols, Yori; Ries, Bernard; Chudnovsky, Maria (2011), Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part II. Nontrivial strip-structures, Discrete Applied Mathematics, 159, 17, p. 1996-2029. http://dx.doi.org/10.1016/j.dam.2011.06.031
Type
Article accepté pour publication ou publiéDate
2011Journal name
Discrete Applied MathematicsVolume
159Number
17Publisher
Elsevier
Pages
1996-2029
Publication identifier
Metadata
Show full item recordAbstract (EN)
Stronglyperfectgraphs 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.Subjects / Keywords
Structural graph theory; Wireless networking; Stronglyperfectgraphs; Forbidden induced subgraphs; Claw-freegraphsRelated items
Showing items related by title and author.
-
Ries, Bernard; Chudnovsky, Maria; Zwols, Yori (2011) Article accepté pour publication ou publié
-
Birand, Berk; Chudnovsky, Maria; Ries, Bernard; Seymour, Paul; Zussman, Gil; Zwols, Yori (2012) Article accepté pour publication ou publié
-
Zussman, Gil; Seymour, Paul; Zwols, Yori; Birand, Berk; Ries, Bernard; Chudnovsky, Maria (2010) Communication / Conférence
-
Diner, Öznur Yaşar; Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard (2018) Article accepté pour publication ou publié
-
Dereniowski, Dariusz; Kubiak, W.; Ries, Bernard; Zwols, Yori (2013) Article accepté pour publication ou publié