Kernel list-coloring lemma
ID: kernel-list-coloring-lemma
In a kernel-perfect directed graph, lists of size at least admit a proper graph coloring. Choose a color and a digraph kernel in the subgraph on vertices whose lists contain . Color that kernel , delete it, and remove from the remaining lists. Every vertex losing a color also loses an outgoing neighbour; hence the inequality persists. Induction on the vertex count finishes the proof.
New to topics? Read the docs here!