𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of restricted graph homomorphisms

✍ Scribed by Richard C. Brewster; Pavol Hell; Gary MacGillivray

Book ID
108316085
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
529 KB
Volume
167-168
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ 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 homomorphisms to direct pr
Complexity of homomorphisms to direct products of graphs
✍ Judit BΓΌki; Csaba SzabΓ³ πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 55 KB

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.

Complexity of tree homomorphisms
Complexity of tree homomorphisms
✍ P. Hell; J. NeΕ‘etΕ™il; X. Zhu πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 704 KB