کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648190 | 1342397 | 2012 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Critically paintable, choosable or colorable graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We extend results about critically k-colorable graphs to choosability and paintability (list colorability and on-line list colorability). Using a strong version of Brooks' Theorem, we generalize Gallai's Theorem about the structure of the low-degree subgraph of critically k-colorable graphs, and introduce a more adequate lowest-degree subgraph. We prove lower bounds for the edge density of critical graphs, and generalize Heawood's Map-Coloring Theorem about graphs on higher surfaces to paintability. We also show that on a fixed given surface, there are only finitely many critically k-paintable/k-choosable/k-colorable graphs, if kâ¥6. In this situation, we can determine in polynomial time k-paintability, k-choosability and k-colorability, by giving a polynomial time coloring strategy for “Mrs. Correct”. Our generalizations of k-choosability theorems also concern the treatment of non-constant list sizes (non-constant k). Finally, we use a Ramsey-type lemma to deduce all 2-paintable, 2-choosable, critically 3-paintable and critically 3-choosable graphs, with respect to vertex deletion and to edge deletion.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 22, 28 November 2012, Pages 3373-3383
Journal: Discrete Mathematics - Volume 312, Issue 22, 28 November 2012, Pages 3373-3383
نویسندگان
Ayesha Riasat, Uwe Schauz,