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.


dimacs-www@dimacs.rutgers.edu
Document last modified on April 28, 1995