A graph theoretic proof of the complexity of colouring by a local tournament with at least two directed cycles

Gary MacGillivray, Jacobus Swarts, Jørgen Bang-Jensen

Abstract


In this paper we give a graph theoretic proof of the fact that deciding whether a homomorphism exists to a fixed local tournament with at least two directed cycles is NP-complete. One of the main reasons for the graph theoretic proof is that it showcases all of the techniques that have been built up over the years in the study of the digraph homomorphism problem.

Full Text: PDF

PID: http://hdl.handle.net/10515/sy5mc8rw8

Contributions to Discrete Mathematics. ISSN: 1715-0868