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!