THE EFFECT OF 2 CYCLES ON THE COMPLEXITY OF COLOURINGS BY DIRECTED-GRAPHS

被引：47

作者：

BANGJENSEN, J ^{[1
]}

HELL, P ^{[1
]}

机构：

[1] SIMON FRASER UNIV,SCH COMP SCI,BURNABY V5A 1S6,BC,CANADA

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 26卷 / 01期

关键词：

D O I：

10.1016/0166-218X(90)90017-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. © 1990.

引用

页码：1 / 23

页数：23