Fractionally and integrally co-strongly perfect claw-free graphs
<-- Return to the list
Date: 11-10-2009
Start Time:
3:00pm
End Time: 4:00pm
Speaker: Yori Zwols, Columbia University
Location: Mudd 303
ABSTRACT
Strongly perfect graphs have been studied by several authors (e.g. Berge, Duchet, Ravindra, Wang). This talk deals with 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 fractionally co-strongly perfect graphs 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 by a path of arbitrary length in a certain way. Wang gave a characterization of strongly perfect claw-free graph. As a corollary claw-free graphs whose complements are strongly perfect.
This is joint work with Maria Chudnovsky and Bernard Ries.