Perfect graphs are kernel solvable Original Research Article

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.