×

On the complexity of colouring by superdigraphs of bipartite graphs. (English) Zbl 0783.05047

Summary: Let \(H\) be a directed graph whose vertices are called colours. An \(H\)- colouring of a digraph \(G\) is an assignment of these colours to the vertices of \(G\) so that if \(g\) is adjacent to \(g'\) in \(G\) then colour\((g)\) is adjacent to colour\((g')\) in \(H\) (i.e., a homomorphism \(G \to H)\). In this paper we continue the study of the \(H\)-colouring problem, that is, the decision problem ‘Is there an \(H\)-colouring of a given digraph \(G?\)’ It follows from a result of P. Hell and J. Nešetřil [J. Comb. Theory, Ser. B 48, No. 1, 92-110 (1990; Zbl 0639.05023)] that this problem is NP-complete whenever \(H\) contains a symmetric odd cycle. We consider digraphs for which the symmetric part of \(H\) is bipartite, that is, digraphs \(H\) which can be constructed from the equivalence digraph of an undirected bipartite graph by adding some arcs. We establish some sufficient conditions for these \(H\)-colouring problems to be NP-complete. A complete classification is established for the subclass of ‘partionable digraphs’, which we introduce.

MSC:

05C15 Coloring of graphs and hypergraphs
68Q25 Analysis of algorithms and problem complexity
05C20 Directed graphs (digraphs), tournaments
68R10 Graph theory (including graph drawing) in computer science
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., On the complexity of generalized colourings of directed graphs (1989), Odense Universitet, Institut for Matematik og Datalogi, No. 3
[3] Bang-Jensen, J.; Hell, P., The effect of two cycles on the complexity of colourings by directed graphs, Discrete Appl. Math., 26, 1-23 (1990) · Zbl 0697.05029
[4] 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
[5] Bang-Jensen, J.; Hell, P.; MacGillivray, G., Hereditarily hard colouring problems (1989), preprint · Zbl 0816.68090
[6] Bloom, G.; Burr, S., On unavoidable digraphs in orientations of graphs, J. Graph Theory, 11, 453-462 (1987) · Zbl 0647.05025
[7] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Elsevier: Elsevier New York · Zbl 1134.05001
[8] Brouwer, A. E.; Veldman, H. J., Contractability and NP-completeness, J. Graph Theory, 11, 71-79 (1987) · Zbl 0603.05016
[9] Cook, S., On the complexity of theorem proving procedures, (proc. 3rd ACM Symp. on Theory of Computing (1971), ACM New York), 151-158
[10] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[11] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph colourings, Discrete Appl. Math., 35, 29-46 (1992)
[12] Gutjahr, W., Ph.D. Thesis (1989), Technical University of Graz: Technical University of Graz Graz, Austria
[13] 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
[14] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[15] Lovász, L., Coverings and colorings of hypergraphs, Proc. 4th Southeast Conf. on Combinatorics. Proc. 4th Southeast Conf. on Combinatorics, Graph Theory and Computing (1973) · Zbl 0322.05114
[16] Nešetřil, J.; Pultr, A., On classes of relations determined by subobjects and factorobjects, Discrete Math., 22, 287-300 (1978) · Zbl 0388.05039
[17] MacGillivaray, G., The complexity of generalized colourings, (Ph.D. Thesis (1989), Simon Fraser University: Simon Fraser University Burnaby, B.C., Canada)
[18] MacGillivary, G., On the complexity of colourings by vertex-transitive and arc-transitive digraphs, SIAM J. Discrete Math., 4, 397-408 (1991)
[19] Maurer, H. A.; Sudborough, J. H.; Welzl, E., On the complexity of the general colouring problem, Inform. Control, 51, 123-145 (1981) · Zbl 0502.68015
[20] Schaefer, T. J., The complexity of satisfiability problems, Proc. 10th ACM Symp. on Theory of Computing, 216-226 (1978) · Zbl 1282.68143
[21] Welzl, E., Colour families are dense, Theoret. Comput. Sci., 17, 29-41 (1982) · Zbl 0482.68063
[22] E. Welzl, Personal communication.; E. Welzl, Personal communication.
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.