Université de Fribourg

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

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

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

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

Université de Fribourg

Claw-free graphs with strongly perfect complements : Fractional and integral version. Part I. Basic graphs

Chudnovsky, Maria ; Ries, Bernard ; Zwols, Yori

In: Discrete Applied Mathematics, 2011, vol. 159, no. 17, p. 1971-1995

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). 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-free graphs that are fractionally strongly perfect in the...