Tuesday, June 18
Perfect Graphs have engaged the interest of researchers from both the theoretical and the algorithmic standpoint. This class of graphs is known to have a vast array of practical applications. The class of AT-free graphs has been studied in conjuction with the intuitive notion of a "linear structure" apparent in many familes of (not necessarily perfect) graphs.
In the realm of perfect graphs research has been conducted essentially in two directions: the first one involves revealing structural properties of this class of graphs. Although initially motivated by an attempt at proving Berge's Strong Perfect Graph Conjecture, this direction has now outgrown its original scope and agenda.
The second line of research, not necessarily disjoint from the first one, involves the algorithmic study of perfect graphs and of various classes thereof.
On the other hand, interest in the class of Asteroidal Triple-free Graphs (AT-free graphs) is more recent and has been motivated, in part, by an attempt at understanding the "agent" responsible for the linear structure that is apparent in many classes of graphs.
Potential applications range from molecular biology, to network design, to name a few.
Advances in Perfect and AT-free Graphs
Organizer: Stephan Olariu
Old Dominion University
- 1:30 On Graphs with Hypertree Structure and Their Algorithmic Use
- Andreas Brandstaedt, University of Rostock, Germany
- 2:00 Reducible Cliques and the Strong Perfect Graph Conjecture
- Antonio Sassano, University of Rome "La Sapienza", Italy
- 2:30 New Results on AT-free Graphs
- Lorna Stewart, University of Alberta, Canada
- 3:00 Perfectly Contractile Graphs
- Frederic Maffray, Laboratoire IMAG, France