A note on kernels and Sperner's Lemma
2009
The kernel-solvability of perfect graphs was first proved by Boros and Gurvich, and later Aharoni and Holzman gave a shorter proof. Both proofs were based on Scarf's Lemma. In this note we show that a very simple proof can be given using a polyhedral version of Sperner's Lemma. In addition, we extend the Boros-Gurvich theorem to h-perfect graphs and to a more general setting.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
15
Citations
NaN
KQI