کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653612 | 1632783 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Short proofs of coloring theorems on planar graphs
ترجمه فارسی عنوان
شواهد کوتاه از قضیه های رنگ آمیزی بر روی نمودارهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A lower bound on the number of edges in a kk-critical nn-vertex graph recently obtained by Kostochka and Yancey yields a half-page proof of the celebrated Grötzsch Theorem that every planar triangle-free graph is 3-colorable. In this paper we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among which is the Grünbaum–Aksenov Theorem that every planar graph with at most three triangles is 33-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most 4 is 33-colorable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 314–321
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 314–321
نویسندگان
Oleg V. Borodin, Alexandr V. Kostochka, Bernard Lidický, Matthew Yancey,