Bang-Jensen, Jørgen; Hell, Pavol; MacGillivray, Gary The complexity of colouring by semicomplete digraphs. (English) Zbl 0678.05018 SIAM J. Discrete Math. 1, No. 3, 281-298 (1988). Summary: The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping f: V(D)\(\to V(H)\) such that (f(x),f(y)) is an edge of H whenever (x,y) is an edge of D. The H- colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise. Cited in 1 ReviewCited in 37 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C20 Directed graphs (digraphs), tournaments 68Q25 Analysis of algorithms and problem complexity Keywords:graph colouring; graph homomorphism; complexity; polynomial algorithm; NP-completeness; tournaments; H-colouring problem; directed graph; semicomplete digraphs; T-colouring problem PDFBibTeX XMLCite \textit{J. Bang-Jensen} et al., SIAM J. Discrete Math. 1, No. 3, 281--298 (1988; Zbl 0678.05018) Full Text: DOI