# Decomposing graph homomorphisms

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?

• 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.) – a3nm Apr 13 at 15:39
• Thank you for the reference! – A. D. Apr 14 at 9:04