کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777097 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Irreducible 4-critical triangle-free toroidal graphs
ترجمه فارسی عنوان
نمودارهای ناپایدار 4-بحرانی بدون تردید بدون مثلث
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی گراف نمودارهای توریدال، نمودارهای بدون مثلث،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The theory of DvoÅák, Král', and Thomas [DvoÅák, Z., D. Král', and R. Thomas, Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs, ArXiv e-prints 1404.6356v2 (Jan. 2015)] shows that a 4-critical triangle-free graph embedded in the torus has only a bounded number of faces of length greater than 4 and that the size of these faces is also bounded. We study the natural reduction in such embedded graphs-identification of opposite vertices in 4-faces. We give a computer-assisted argument showing that there are exactly four 4-critical triangle-free irreducible toroidal graphs in which this reduction cannot be applied without creating a triangle. Using this result, we show that every 4-critical triangle-free graph embedded in the torus has at most four 5-faces, or a 6-face and two 5-faces, or a 7-face and a 5-face, in addition to at least seven 4-faces. This result serves as a basis for the exact description of 4-critical triangle-free toroidal graphs, which we present in a followup paper.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 383-389
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 383-389
نویسندگان
ZdenÄk DvoÅák, Jakub Pekárek,