Campus Event Calendar
Event Entry
What and Who
News on the Stable Set Polytope of Claw-free Graphs
PD Dr. Friedrich Eisenbrand
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 2 December 2004
13:00
-- Not specified --
45
016
Saarbrücken
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.
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.
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.
Contact
--email hidden
passcode not visible
logged in users only
Bahareh Kadkhodazadeh, 11/26/2004 09:55
Bahareh Kadkhodazadeh, 10/21/2004 12:43 -- Created document.
Bahareh Kadkhodazadeh, 10/21/2004 12:43 -- Created document.