
Discrete Mathematics and Optimization Seminar

Jan. 18th, 2010
Fractionally costrongly perfect clawfree graphs. Fractional
and integral version.
Yori Zwols
Columbia

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 clawfree graphs that are fractionally
strongly perfect in the complement. We obtain a forbidden induced
subgraph characterization and display graphtheoretic properties of
such graphs. It turns out that the forbidden induced subgraphs that
characterize clawfree fractionally costrongly 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 clawfree graph. As a corollary
we obtain a characterization of clawfree graphs whose complements
are strongly perfect. This is joint work with Maria Chudnovsky and
Bernard Ries



