Seminario Interdipartimentale di Algoritmica  

Monday, April 11, 2005, 12:00 noon
The stable set polytope of quasiline graphs
Friedrich Eisenbrand
Max Planck Institute fuer Informatik

DIS - Department of Computer and System Sciences
C3 Room, second floor

Abstract:

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. For the class of quasi-line graphs, there exists a conjecture which is called Ben Rebea's conjecture. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have $0/1$~normal vectors. In this talk I discuss Ben Rebea's conjecture and give an outline on how it has been recently proved.

Joint work with: Gianpaolo Oriolo, Gautier Stauffer and Paolo Ventura