×

The effect of two cycles on the complexity of colourings by directed graphs. (English) Zbl 0697.05029

Let H be a fixed digraph. An H-colouring of a digraph D is a mapping f: V(D)\(\to V(H)\) such that if xy is an arc in D then f(x)f(y) is an arc in H. The authors discuss various classes of digraphs H in which the existence of two directed cycles makes the H-colouring problem NP-hard.
Reviewer: J.W.Moon

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M.; Catlin, P.; Gibbons, L., Homomorphisms of 3-chromatic graphs II, Congr. Numer., 47, 19-28 (1985)
[2] Bang-Jensen, J.; Hell, P.; MacGillivray, G., The complexity of colourings by semicomplete digraphs, SIAM J. Discrete Math., 1, 281-298 (1988) · Zbl 0678.05018
[3] J. Bang-Jensen, P. Hell and G. MacGillivray, On the complexity of colouring by supergraphs of bipartite graphs (to appear).; J. Bang-Jensen, P. Hell and G. MacGillivray, On the complexity of colouring by supergraphs of bipartite graphs (to appear). · Zbl 0783.05047
[4] J. Bang-Jensen, P. Hell and G. MacGillivray, Hereditarily hard colouring problems, to appear.; J. Bang-Jensen, P. Hell and G. MacGillivray, Hereditarily hard colouring problems, to appear. · Zbl 0816.68090
[5] Bloom, G.; Burr, S., On unavoidable digraphs in orientations of graphs, J. Graph Theory, 11, 453-462 (1987) · Zbl 0647.05025
[6] Edmonds, J., Edge-disjoint branchings, (Combinatorial Algorithms (1973), Algorithmic Press: Algorithmic Press New York), 91-96
[7] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[8] W. Gutjahr, E. Welzl and G. Woeginger, Polynomial graph-colorings, Tech. Rept. B-88-06, Freie Universität Berlin.; W. Gutjahr, E. Welzl and G. Woeginger, Polynomial graph-colorings, Tech. Rept. B-88-06, Freie Universität Berlin.
[9] Häggkvist, R.; Hell, P.; Miller, D. J.; Neuman Lara, V., On multiplicative graphs and the product conjecture, Combinatorica, 8, 63-74 (1988) · Zbl 0657.05028
[10] P. Hell and J. Nešetřil, On the complexity of \(H\); P. Hell and J. Nešetřil, On the complexity of \(H\)
[11] MacGillivray, G., The complexity of generalized colourings, (Ph.D. Thesis (1989), Department of Mathematics, Simon Fraser University)
[12] Maurer, H. A.; Sudborough, J. H.; Welzl, E., On the complexity of the general colouring problem, Inform. and Control, 51, 123-145 (1981) · Zbl 0502.68015
[13] Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factor-objects, Discrete Math., 22, 287-300 (1978) · Zbl 0388.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.