# 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