کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903482 1632569 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Correspondence Homomorphisms to Reflexive Graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Correspondence Homomorphisms to Reflexive Graphs
چکیده انگلیسی
Correspondence homomorphisms are a common generalization of homomorphisms and of correspondence colourings. For a fixed reflexive target graph H, the problem is to decide whether an input graph G, with each edge labeled by a pair of permutations of V(H), admits a homomorphism to H 'corresponding' to the labels. We classify the complexity of this problem as a function of H. It turns out that there is dichotomy-each of the problems is polynomial or NP-complete. While most graphs H yield NP-complete problems, there is an interesting polynomial case when the problem can be solved by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 9-14
نویسندگان
, ,