Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:News on the Stable Set Polytope of Claw-free Graphs
Speaker:PD Dr. Friedrich Eisenbrand
coming from:
Speakers Bio:
Event Type:Ringvorlesung
Visibility:D1, D2, D3, D4, D5
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 2 December 2004
Duration:-- Not specified --
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.

 Such a conjecture   exists for the
 class of  quasi-line graphs.  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. Ben Rebea's conjecture states that the
 stable set polytope of a quasi-line graph is completely described by
 clique-family inequalities.  Chudnovsky and Seymour   recently
 provided a decomposition result for claw-free graphs and proved that
 Ben Rebea's conjecture holds, if the quasi-line graph is not a fuzzy
   circular interval graph.

 In this paper, we give a proof of Ben Rebea's conjecture by showing
 that it also holds for fuzzy circular interval graphs. Our result  builds
 upon  an algorithm of Bartholdi, Orlin and Ratliff which is
 concerned with  integer programs defined by circular ones matrices.
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Bahareh Kadkhodazadeh, 11/26/2004 09:55 AM
  • Bahareh Kadkhodazadeh, 10/21/2004 12:43 PM -- Created document.