DIMACS Discrete Mathematics Seminar


Perfect Graphs are Kernel Solvable


Endre Boros
RUTCOR, Rutgers University


DIMACS Seminar Room, CoRE Building, Room 431
Busch Campus, Rutgers University


4:30 PM
Tuesday, May 2, 1995


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