×

Counting list homomorphisms for graphs with bounded degrees. (English) Zbl 1059.05049

Nešetřil, J. (ed.) et al., Graphs, morphisms and statistical physics. Proceedings of the workshop held at Rutgers University, Piscataway, NJ, USA, March 19–21, 2001. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3551-3/hbk). DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 63, 105-112 (2004).
A homomorphism from a graph \(G\) to a graph \(H\) is a mapping from the vertices of \(G\) to the vertices of \(H\) which sends each edge of \(G\) to an edge of \(H\). When \(H\) is the complete graph \(K_n\), this is nothing more than a proper \(n\)-colouring of \(G\). The idea of list homomorphisms generalises the notion of list colouring by assigning to each vertex of \(G\) a list of permitted images in \(H\).
The authors consider the computational complexity of 8 variants of the homomorphism problem; in each of them \(H\) is fixed and \(G\) is part of the instance of the problem. The 8 variants are found by varying (i) whether we are looking for homomorphisms or list homomorphisms, (ii) whether we want to count the homomorphisms or just decide if one exists, (iii) whether or not an upper bound is imposed on the maximum degree in \(G\). Surveys are given for the six of these variants which had previously been solved by the authors and their collaborators or by M. Dyer and C. Greenhill [Random Struct. Algorithms 17, 260–289 (2000; Zbl 0965.68073), and Random Struct. Algorithms 25, 346–352 (2004; Zbl 1089.68076)]. The remaining two problems, namely counting list homomorphisms with or without a degree constraint, are solved here. The answer, of course, is that these problems are \(\#P\)-complete except in very special circumstances.
For the entire collection see [Zbl 1051.05003].

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite