Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648884 | Discrete Mathematics | 2010 | 10 Pages |
Abstract
In this paper we establish a dichotomy theorem for the complexity of homomorphisms to fixed locally semicomplete digraphs. It is also shown that the same dichotomy holds for list homomorphisms. The polynomial algorithms follow from a different, shorter proof of a result by Gutjahr, Welzl and Woeginger.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jørgen Bang-Jensen, Gary MacGillivray, Jacobus Swarts,