Recent problems and results about kernels in directed graphs (Q2640613): Difference between revisions

A directed graph G is kernel-perfect if all its induced subgraphs have kernels. Suppose each edge of a simple graph G is replaced by an arc or by a pair of oppositely-oriented arcs in such a way that every clique contains a vertex which is successor of all its other vertices; if the resulting graph is always kernel-perfect then G is said to be quasi- perfect. The authors discuss some results concerning kernel-perfect and quasi-perfect graphs; in particular, they conjecture that a graph is quasi-perfect if and only if it is perfect.