<p>A homomorphism <span class="math-container">$h: G\to H$</span> from a graph <span class="math-container">$G$</span> to a graph <span class="math-container">$H$</span> is a function from the vertices of <span class="math-container">$G$</span> to those of <span class="math-container">$H$</span> which preserves edges, that is, if <span class="math-container">$(x,y)$</span> is an edge of <span class="math-container">$G$</span> then <span class="math-container">$(h(x),h(y))$</span> is an edge of <span class="math-container">$H$</span>.</p>
<p>A homomorphism induces an equivalence class on the vertices of <span class="math-container">$G$</span>: two vertices are equivalent if they are mapped to the same vertex. We say that a <strong>homomorphism identifies at most two vertices</strong> if all the equivalence classes are singletons except one which may possibly contain two vertices.</p>
<p>A decomposition of a homomorphism <span class="math-container">$h: G \to H$</span> is a sequence of graphs <span class="math-container">$G=G_0, G_1,..,G_n=H$</span> such that:</p>
<ul>
<li><p>For every <span class="math-container">$i\in[0,n-1]$</span>, there is a homomorphism <span class="math-container">$h_i:G_i \to G_{i+1}$</span> which identifies at most two vertices.</p>
</li>
<li><p><span class="math-container">$h=h_{n-1}\circ \dots \circ h_0$</span> .</p>
</li>
</ul>
<p>The width of such decomposition is the maximum tree-width of the graphs <span class="math-container">$G_i, i\in[1,n]$</span>.</p>
<p>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:</p>
<p><strong>Conjecture:</strong>   For every integer <span class="math-container">$k$</span>, there is  <span class="math-container">$k'$</span> such that every homomorphism between graphs of tree-width <span class="math-container">$k$</span> admits a decomposition of width <span class="math-container">$k'$</span>.</p>
<p>At the beginning, my conjecture was that <span class="math-container">$k'=k$</span>, that is, every homomorphism between graphs of tree-width <span class="math-container">$k$</span> can be decomposed without exiting the class of tree-width <span class="math-container">$k$</span> graphs. But for certain homomorphisms between graphs of tree-width <span class="math-container">$2$</span>, every decomposition is of width at least <span class="math-container">$3$</span>.</p>
<p>Do you know this problem? Do you have bibliographical recommendations which can help me attack this problem?</p>

CC BY-SA 4.0
2021-04-13T15:39:23.567Z
Nice question! I have an old question which is somewhat related: https://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.)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-04-14T09:04:52.873Z
Thank you for the reference!
A. D.
<graph-theory><homomorphism>
Decomposing graph homomorphisms
A. D.
# Decomposing graph homomorphisms

(Asked by: username_0 on 2021-04-12)

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?

**Tags:** graph-theory, homomorphism

> **Comments:**
> **username_1**: Nice question! I have an old question which is somewhat related: https://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.)  
> **username_0**: Thank you for the reference!  

---

## 0 answers

