DIMACS Discrete Mathematics Seminar
Title:
Perfect Graphs are Kernel Solvable
Speaker:
- Endre Boros
- RUTCOR, Rutgers University
Place:
- DIMACS Seminar Room, CoRE Building, Room 431
- Busch Campus, Rutgers University
Time:
- 4:30 PM
- Tuesday, May 2, 1995
Abstract:
Let G be a graph, and let D denote an over-orientation of G,
i.e. D is a directed graph obtained from G by orienting all
of its edges (bidirected edges are allowed). A subset S of V
is called a kernel of D if S is stable (independent)
in G and every vertex outside S has a successor in S.
We say that a clique C of G has a kernel, if there is a vertex v
in C which is the successor of all other vertices of C.
Finally, a graph G is called kernel-solvable if
for every over-orientation D of G for which every clique of G
has a kernel, the directed graph D itself has a kernel.
Using strong result from game theory, we prove a conjecture
of Berge and Duchet (1983), by showing that perfect graphs are kernel
solvable. The converse was also conjectured, and is still open.
We can show in that direction that a kernel solvable graph always
has a perfect ``blow-up'' (obtained by substituting some of the
vertices by cliques).
Joint work with V. Gurvich.
Document last modified on April 28, 1995