کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420280 | 683915 | 2010 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A polyhedral embedding in a surface is one in which any two faces have boundaries that are either disjoint or simply connected. In a cubic (3-regular) graph this is equivalent to the dual being a simple graph. In 1968, Grünbaum conjectured that every cubic graph with a polyhedral embedding in an orientable surface is 3-edge-colorable. For the sphere, this is equivalent to the Four-Color Theorem, but we have disproved the conjecture in the general form. In this paper we extend this result and show that if we restrict our attention to a class of cubic graphs with a polyhedral embedding in an orientable surface, then the computational complexity of the 3-edge-coloring problem and its approximation does not improve.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 16, 28 August 2010, Pages 1856–1860
Journal: Discrete Applied Mathematics - Volume 158, Issue 16, 28 August 2010, Pages 1856–1860
نویسندگان
Martin Kochol,