94-32 Perfect Graphs are Kernel Solvable

DIMACS TR: 94-32

Perfect Graphs are Kernel Solvable

Authors: Endre Boros and Vladimir Gurvich

ABSTRACT
In this paper we prove that perfect graphs are kernel solvable, as it was conjectured by Berge and Duchet (1983). The converse statement, i.e. that kernel solvable graphs are perfect, was also conjectured in the same paper, and is still open. In this direction we prove that it is always possible to substitute some of the vertices of a non-perfect graph by cliques so that the resulting graph is not kernel solvable.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-32.ps

DIMACS Home Page