A homomorphism $h: G\to H$ from a graph $G$ to a graph $H$ is a function from the vertices of $G$ to those of $H$ which preserves edges, that is, if $(x,y)$ is an edge of $G$ then $(h(x),h(y))$ is an edge of $H$.

A homomorphism induces an equivalence class on the vertices of $G$: two vertices are equivalent if they are mapped to the same vertex. We say that a homomorphism identifies at most two vertices if all the equivalence classes are singletons except one which may possibly contain two vertices.

A decomposition of a homomorphism $h: G \to H$ is a sequence of graphs $G=G_0, G_1,..,G_n=H$ such that:

  • For every $i\in[0,n-1]$, there is a homomorphism $h_i:G_i \to G_{i+1}$ which identifies at most two vertices.

  • $h=h_{n-1}\circ \dots \circ h_0$ .

The width of such decomposition is the maximum tree-width of the graphs $G_i, i\in[1,n]$.

Of course, any homomorphism between two graphs of tree-width k can be decomposed, but I do not know if I can bind the tree-width of the intermediary graphs. I am wondering then if the following result is true:

Conjecture: For every integer $k$, there is $k'$ such that every homomorphism between graphs of tree-width $k$ admits a decomposition of width $k'$.

At the beginning, my conjecture was that $k'=k$, that is, every homomorphism between graphs of tree-width $k$ can be decomposed without exiting the class of tree-width $k$ graphs. But for certain homomorphisms between graphs of tree-width $2$, every decomposition is of width at least $3$.

Do you know this problem? Do you have bibliographical recommendations which can help me attack this problem?

  • $\begingroup$ Nice question! I have an old question which is somewhat related: cstheory.stackexchange.com/q/34877. (It won't answer yours, but it is also asking about homomorphisms from treewidth-k graphs to treewidth-k graphs.) $\endgroup$
    – a3nm
    Apr 13, 2021 at 15:39
  • $\begingroup$ Thank you for the reference! $\endgroup$
    – A. D.
    Apr 14, 2021 at 9:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.