|
|
Discrete Mathematics and Optimization Seminar
|
Jan. 18th, 2010
|
Fractionally co-strongly perfect claw-free 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 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
we obtain a characterization of claw-free graphs whose complements
are strongly perfect. This is joint work with Maria Chudnovsky and
Bernard Ries
|
|
|
|