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.