Department of Mathematics

Indian Institute Of Technology Madras , Chennai

Forbidden Induced Subgraph Characterizations

Speaker : Dr. Vaidyanathan Sivaraman, University of 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.

Key Speaker Dr. Vaidyanathan Sivaraman, University of Binghamton.
Place Madhava Hall
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None