Lokálně injektivní homomorfismy: listy zajišťují dichotomii

Abstrakt

V článku ukazujeme, že listová verze problému existence lokálně injektivního homomorfismu je vždy buď NP=úplná nebo polynomiálně řešitelná, a to v závislosti na parametru problému.

Klíčová slova

• Locally
• injective
• graph
• homomorphism
• Lists
• guarantee
• dichotomy