= Kernel list-coloring lemma
{title2=$|L(v)|\ge d^+(v)+1$}
In a <kernel-perfect directed graph>, lists of size at least $d^+(v)+1$ admit a proper <graph coloring>. Choose a color $a$ and a <digraph kernel> in the subgraph on vertices whose lists contain $a$. Color that kernel $a$, delete it, and remove $a$ 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.
Back to article page
