On kernels in perfect graphs (Q684411): Difference between revisions

By a kernel of a digraph \(D\) is meant a set of vertices which is both independent and absorbant. In 1988, \textit{C. Berge} and \textit{P. Duchet} conjectured that an undirected graph \(G\) is perfect iff for an orientation \(D\) of \(G\) (where pairs of opposite arcs are allowed), if every clique of \(D\) has a kernel then \(D\) itself has a kernel. This paper shows that the conjecture is true for the complements of strongly perfect graphs and that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.