Graphs without long holes
Prof. R. Sritharan
University of Dayton, U.S.A.
11-07-01

---

Abstract

A hole in a graph is an induced cycle on four or more vertices. Classes of graphs in which long holes are forbidden have been studied in the context of perfect graphs. In this talk we discuss results on certain classes of graphs that do not contain long holes. In particular, we present results on weakly chordal graphs, their generalizations, and some restrictions. The issues addressed will be structural (such as characterization) as well as algorithmic (such as recognition, optimization).