Perfect graphs are kernel solvable

A superorientation (direction) of a graph \(G\) is a directed graph \(D\) whose underlying undirected graph is \(G\), where pairs of reversible arcs are allowed. A subset \(S\) of the vertices of a directed graph \(D\) is called a kernel if it is a stable set and every vertex outside \(S\) has a successor in \(S\). A superorientation of \(D\) is said to be admissible if every (directed) clique has a kernel. An undirected graph \(G\) is called kernel solvable if every admissible superorientation of \(G\) has a kernel. In this important paper the authors prove, using results of game theory, the following conjecture of C. Berge and P. Duchet from 1983: Every perfect graph is kernel solvable. In addition, they give a partial answer for a second conjecture which states that, conversely, kernel solvable graphs are perfect, in proving that if a graph \(G\) is not perfect, then there exists a blow-up (substituting some vertices by cliques) of \(G\), which is not kernel solvable.

Recommendations

Cites work

Cited in

(35)

This page was built for publication: Perfect graphs are kernel solvable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126176)