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.

Articles by others on the same topic (NaN)

There are currently no matching articles.