Authors
Jørgen Bang-Jensen, Pavol Hell
Publication date
1990/1/1
Journal
Discrete applied mathematics
Volume
26
Issue
1
Pages
1-23
Publisher
North-Holland
Description
Let H be a fixed directed graph. An H-colouring of a directed graph D is a mapping f: V(D)→V(H) such that f(x)f(y) is an edge of H whenever xy is an edge of D. We study the following H-colouring problem:
Instance: A directed graph D.
Question: Does there exist an H-colouring of D?
In an earlier paper [2] it is shown that among semicomplete digraphs H, it is the existence of two directed cycles in H which makes the H-colouring problem (NP-) hard. In this paper we provide further classes of digraphs in which two directed cycles in H make the H-colouring problem NP-hard. These include both classes of dense and of sparse digraphs. There still appears to be no natural conjecture as to what digraphs H give NP-hard H-colouring problems; however, in view of our results, we are led to make such a conjecture for digraphs without sources and sinks.
Total citations
Scholar articles
J Bang-Jensen, P Hell - Discrete applied mathematics, 1990