**Date & Time:** Monday, July 11, 2016, 14:00-15:00

**Venue:** Ramanujan Hall

**Title:**Forbidden Induced Subgraph Characterizations

**Speaker: ** Vaidy Sivaraman, SUNY, Binghamton

**Abstract:** One way to describe a class of graphs closed under taking
induced subgraphs is by listing the set of all forbidden graphs, graphs
that are not in the class but whose every proper induced subgraph is in
the class. Such characterizations are known for some important classes.
The class of perfect graphs is a prime example. I will mention such a
theorem that we discovered recently for a generalization of threshold
graphs. Then I will discuss ongoing work on finding such a
characterization for quasi-triangulated graphs, a class halfway between
chordal and weakly chordal graphs. The difficult question of whether
anything can be said for a general hereditary class will be pointed out.
This is joint work with Richard Behr and Thomas Zaslavsky.