Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part I. Basic graphs
Ries, Bernard; Chudnovsky, Maria; Zwols, Yori (2011), Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part I. Basic graphs, Discrete Applied Mathematics, 159, 17, p. 1971-1995. http://dx.doi.org/10.1016/j.dam.2011.06.024
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
Abstract (EN)Stronglyperfectgraphs have been studied by several authors (e.g. Berge and Duchet (1984) , Ravindra (1984)  and Wang (2006) ). In a series of two papers, the current paper being the first 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)  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 / KeywordsStructural graph theory; Wireless networking; Stronglyperfectgraphs; Forbidden induced subgraphs; Claw-freegraphs
Showing items related by title and author.
Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part II. Nontrivial strip-structures Zwols, Yori; Ries, Bernard; Chudnovsky, Maria (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