کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418459 681673 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the equitable total chromatic number of cubic graphs
ترجمه فارسی عنوان
درباره عدد رنگی کل عادلانه نمودارهای مکعب
کلمات کلیدی
نمودارهای مکعب. رنگ آمیزی کل عادلانه . NP کامل
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. Wang conjectured that the equitable total chromatic number of a multigraph of maximum degree ΔΔ is at most Δ+2Δ+2, and proved this for the case where Δ≤3Δ≤3. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5, and in this work we prove that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.Furthermore, we present the first known Type 1 cubic graphs with equitable total chromatic number 5. All of them have, by construction, a small girth. We also find one infinite family of Type 1 cubic graphs of girth 5 having equitable total chromatic number 4. This motivates the following question: Does there exist Type 1 cubic graphs of girth greater than 5 and equitable total chromatic number 5?

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 84–91
نویسندگان
, , , , , ,