کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419654 | 683846 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on kernels and Sperner’s Lemma
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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 hh-perfect graphs and to a more general setting.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 15, 6 August 2009, Pages 3327–3331
Journal: Discrete Applied Mathematics - Volume 157, Issue 15, 6 August 2009, Pages 3327–3331
نویسندگان
Tamás Király, Júlia Pap,