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?
