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!