Kernel-perfect directed graph
ID: kernel-perfect-directed-graph
A digraph kernel is an independent set of vertices such that each vertex outside has a directed edge from itself to a vertex in . 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.
New to topics? Read the docs here!