Claw-free graphs with strongly perfect complements

Chudnovsky, Maria; Ries, Bernard; Zwols, Yori

doi:10.1016/j.dam.2011.06.031

Back

Journal article

Claw-free graphs with strongly perfect complements : Fractional and integral version, Part II: Nontrivial strip-structures

Chudnovsky, Maria Columbia University, United States
Ries, Bernard University of Fribourg, Switzerland
Zwols, Yori Columbia University, United States

2011

Published in:

Discrete applied mathematics. - 2011, vol. 159, no. 17, p. 1996-2029

Applied Mathematics

Discrete Mathematics and Combinatorics

English 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.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language