[KAIST Discrete Math Seminar] 1/7 FRI 4PM (Ilhee Kim 김일희, Forbidden induced subgraphs of double-split graphs)

[Sang-il Oum]

*HAPPY NEW YEAR 2011*

***** KAIST Discrete Math Seminar *****

DATE: January 7, Friday

TIME: 4PM-5PM

PLACE: E6-1, ROOM 1409

SPEAKER: Ilhee Kim (김일희), PACM, Princeton University, Princeton, NJ, USA

TITLE: Forbidden induced subgraphs of double-split graphs

http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20110107/

In the course of proving the strong perfect graph theorem, Chudnovsky,
Robertson, Seymour, and Thomas showed that every perfect graph either
belongs to one of five basic classes or admits one of several
decompositions. Four of the basic classes are closed under taking
induced subgraphs (and have known forbidden subgraph
characterizations), while the fifth one, consisting of double-split
graphs, is not. A graph is doubled if it is an induced subgraph of a
double-split graph. We find the forbidden induced subgraph
characterization of doubled graphs; it contains 44 graphs.
This is joint work with Boris Alexeev, and Alexandra Fradkin.