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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.