Kratochvíl, Jan; Matematični kolokvij november 2006

Iz MaFiRaWiki

Graph homomorphisms: From frequency assignment to constraint satisfaction

Jan Kratochvíl

Karlova univerza v Pragi

23. november 2006


Graph homomorphisms are edge-preserving vertex-mappings of graphs. As such, they map the neighborhood of each vertex of the source graph into the neighborhood of its image in the target graph. We call a homomorphism locally bijective (injective, surjective) if for each vertex, the restricted mapping from its neighborhood into the neighborhood of its image is bijective (injective, surjective, respectively). This concept of local constraints provides a unifying view onto several previously defined and studied graph invariants.

We will first show the connection to role assignments, graph covers and, perhaps most surprisingly, to generalized L(2,1)-labelings of graphs. Our main concern will be the computational complexity of deciding if an input graph G allows a homomorphism of a specific type into a parameter graph H. For some variants of the problem, only partial results are known. However, in the case of locally surjective homomorphisms, and as the most recent result, in the case of the list version of the locally injective homomorphsims, complete characterizations have been obtained. In both cases a full polynomial/NP-complete dichotomy (based on the parameter graph H) holds.

Glej tudi

Matematični kolokviji

Osebna orodja