𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity of homomorphisms to direct products of graphs

✍ Scribed by Judit Büki; Csaba Szabó

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
55 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

For a graph G, OAL G asks whether or not an input graph H together with a partial map g :

G 2 are trees and NP-complete otherwise.

📜 SIMILAR VOLUMES

Bi-arc graphs and the complexity of list
Bi-arc graphs and the complexity of list homomorphisms
✍ Tomas Feder; Pavol Hell; Jing Huang 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract Given graphs __G__, __H__, and lists __L__(__v__) ⊆ __V__(__H__), __v__ ε __V__(__G__), a list homomorphism of __G__ to __H__ with respect to the lists __L__ is a mapping __f__ : __V__(__G__) → __V__(__H__) such that __u__v ε __E__(__G__) implies __f__(__u__)__f__(__v__) ε __E__(__H__),

Complexity of tree homomorphisms
Complexity of tree homomorphisms
✍ P. Hell; J. Nešetřil; X. Zhu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 704 KB
Direct products of automorphism groups o
Direct products of automorphism groups of graphs
✍ Mariusz Grech 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract In this article we study the product action of the direct product of automorphism groups of graphs. We generalize the results of Watkins [J. Combin Theory 11 (1971), 95–104], Nowitz and Watkins [Monatsh. Math. 76 (1972), 168–171] and W. Imrich [Israel J. Math. 11 (1972), 258–264], and w