TY - JOUR

T1 - Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II

T2 - Nontrivial strip-structures

AU - Chudnovsky, Maria

AU - Ries, Bernard

AU - Zwols, Yori

N1 - Funding Information:
The first author was partially supported by NSF grant DMS-0758364 . This research was performed while the second author was at Columbia University and at the University of Warwick. This research was performed while the third author was at Columbia University.

PY - 2011/10/28

Y1 - 2011/10/28

N2 - Strongly perfect graphs 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-free graphs that are fractionally strongly perfect 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-free graphs that are fractionally strongly perfect 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 strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.

AB - Strongly perfect graphs 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-free graphs that are fractionally strongly perfect 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-free graphs that are fractionally strongly perfect 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 strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.

KW - Claw-free graphs

KW - Forbidden induced subgraphs

KW - Strongly perfect graphs

KW - Structural graph theory

KW - Wireless networking

UR - http://www.scopus.com/inward/record.url?scp=80052575792&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052575792&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2011.06.031

DO - 10.1016/j.dam.2011.06.031

M3 - Article

AN - SCOPUS:80052575792

VL - 159

SP - 1996

EP - 2029

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 17

ER -