×

List homomorphisms to reflexive graphs. (English) Zbl 0904.05078

Let \(H\) be a fixed graph. In analogy to list colouring problems, we introduce the following list homomorphism problem: Given an input graph \(G\) and for each vertex \(v\) of \(G\) a ‘list’ \(L(v) \subseteq V(H)\), decide whether or not there is a homomorphism (edge-preserving mapping of vertices) \(f : G \to H\) such that \(f(v) \in L(v)\) for each \(v \in V(G)\). We discuss this problem primarily in the context of reflexive graphs, i.e., graphs in which each vertex has a loop. We give a polynomial time algorithm to solve the problem when \(H\) is an interval graph and prove that when \(H\) is not an interval graph the problem is NP-complete. If the lists are restricted to induce connected subgraphs of \(H\), we give a polynomial time algorithm when \(H\) is a chordal graph and prove that when \(H\) is not chordal the problem is again NP-complete. We also argue that the complexity of certain other modifications of the problem (including the retract problem) are likely to be difficult to classify. Finally, we mention some newer results, joint with J. Huang, on irreflexive and general graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable, Illinois J. Math., 21, 429-567 (1977) · Zbl 0387.05010
[2] Alon, N.; Tarsi, M., Colourings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049
[3] Bandelt, H. J.; Dahlmann, A.; Schutte, H., Absolute retracts of bipartite graphs, Discrete Appl. Math., 16, 191-215 (1987) · Zbl 0614.05046
[4] Bandelt, H. J.; Farber, M.; Hell, P., Absolute reflexive retracts and absolute bipartite retracts, Discrete Appl. Math., 44, 9-20 (1993) · Zbl 0795.05133
[5] Bang-Jensen, J.; Hell, P., On the effect of two cycles on the complexity of colouring, Discrete Appl. Math., 26, 1-23 (1990) · Zbl 0697.05029
[6] Bang-Jensen, J.; MacGillivray, G.; Hell, P., The complexity of colouring by semicomplete digraphs, SIAM J. on Discrete Math., 1, 281-298 (1988) · Zbl 0678.05018
[7] Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157 (1979)
[8] T. Feder, M. Y. Vardi, Monotonic monadic SNP and constraint satisfaction, 25th Annual ACM Symposium on Theory of Computing, 1993, 612, 622; T. Feder, M. Y. Vardi, Monotonic monadic SNP and constraint satisfaction, 25th Annual ACM Symposium on Theory of Computing, 1993, 612, 622 · Zbl 1310.68086
[9] T. Feder, Classification of homomorphisms to oriented cycles (draft); T. Feder, Classification of homomorphisms to oriented cycles (draft) · Zbl 0982.05097
[10] T. Feder, P. Hell, J. Huang, List homomorphisms and circular arc graphs; T. Feder, P. Hell, J. Huang, List homomorphisms and circular arc graphs · Zbl 0985.05048
[11] T. Feder, P. Hell, J. Huang, List homomorphisms to general graphs; T. Feder, P. Hell, J. Huang, List homomorphisms to general graphs · Zbl 1111.05035
[12] Fleischner, H.; Stiebitz, M., A solution of a colouring problem of P. Erdős, Discrete Math., 101, 39-48 (1992)
[13] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[14] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[15] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph colourings, Discrete Appl. Math., 35, 29-46 (1992)
[16] P. Hell, Retractions de graphes, Université de Montreal, 1972; P. Hell, Retractions de graphes, Université de Montreal, 1972
[17] Hell, P., Retracts in graphs, Graphs and Combinatorics. Graphs and Combinatorics, Lecture Notes in Math., 406 (1974), Springer-Verlag: Springer-Verlag New York/Berlin, p. 291-301
[18] Hell, P.; Nesetril, J., On the complexity of \(H\), J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[19] Hell, P.; Rival, I., Retracts in graphs, Canad. J. Math., 39, 544-567 (1987) · Zbl 0627.05039
[20] Hell, P.; Nesetril, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. Am. Math. Soc., 348, 1281-1297 (1996) · Zbl 0877.05055
[21] Kubale, M., Some results concerning the complexity of restricted colourings of graphs, Discrete Applied Math., 36, 35-46 (1992) · Zbl 0755.05036
[22] Nowakowski, R.; Rival, I., A fixed edge theorem for graphs with loops, J. Graph Theory, 3, 339-350 (1979) · Zbl 0432.05030
[23] Pesch, E., Retracts of Graphs (1988), Athenaeum: Athenaeum Frankfurt am Main · Zbl 0667.05021
[24] Thomassen, C., Every planar graph is five-choosable, J. Comb. Theory Ser. B, 62, 180-181 (1994) · Zbl 0805.05023
[25] N. Vikas, Computational complexity of graph compaction, Simon Fraser University, 1997; N. Vikas, Computational complexity of graph compaction, Simon Fraser University, 1997
[26] Voigt, M., List Colourings of planar graphs, Discrete Math., 120, 215-219 (1993) · Zbl 0790.05030
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.