کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950784 1441039 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
چکیده انگلیسی
Two graph parameters are equivalent if, for every graph class, they are either both bounded or both unbounded. We provide a list of graph parameters equivalent to the acyclic chromatic number, which contains in particular the 2-edge-colored chromatic number. Recently, the CSP dichotomy conjecture has been reduced to the case of 2-edge-colored homomorphism and to the case of 2-vertex-colored homomorphism. Both reductions are rather long and follow the reduction to the case of oriented homomorphism in “Graphs and homomorphisms” by Hell and NeÅ¡etřil. We give another proof for the case of 2-vertex-colored homomorphism via a simple reduction from the case of 2-edge-colored homomorphism. Finally, we prove that deciding if the 2-edge-colored chromatic number of a 2-edge-colored graph is at most 4 is NP-complete, even if restricted to 2-connected subcubic bipartite planar graphs with arbitrarily large girth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 123, July 2017, Pages 42-46
نویسندگان
, ,