= Kernel-perfect directed graph
A <digraph kernel> is an <independent set> $K$ of <vertices> such that each vertex outside $K$ has a <directed edge> from itself to a vertex in $K$. A <directed graph> is kernel-perfect if every <induced subgraph> has a <digraph kernel>. Preference orientations of the <line graph> of a <bipartite graph> are kernel-perfect: a <stable matching in a bipartite graph> is independent in the line graph, and stability supplies the required outgoing edge at every unmatched edge.
Back to article page
