کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
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
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
چکیده انگلیسی

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
نویسندگان
,