No label defined (Q4660723)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2151253
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 2151253

      Statements

      0 references
      0 references
      4 April 2005
      0 references
      graph homomorphism
      0 references
      list colouring
      0 references
      bi-arc graph
      0 references
      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 \textit{M. Dyer} and \textit{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].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references