For finite trees $T\_{1}$ and $T\_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be an embedding of $T\_{1}$ into $T\_{2}$ in the usual graph-theoretical sense (i.e. a homeomorphism) with the extra condition that
$l\_{1}(x)=l\_{1}(y)$ implies $l\_{2}(f(x))=l\_{2}(f(y))$ for all vertices $x,y$ of $T\_{1}$ (where $l\_{1}$, $l\_{2}$ are the labelling function for $T\_{1}$ and $T\_{2}$, respectively). We say that $T\_{1}$ is an equalitiy-preserving minor of $T\_{2}$, written $T\_{1}\prec\_{ep}T\_{2}$ iff there is an equality-preserving embedding $f:T\_{1}\rightarrow T\_{2}$. 
(Note that we do not demand that differently labelled vertices are mapped to differently labelled vertices.)


Is $\prec\_{ep}$ a well-quasi-ordering or even a better-quasi-ordering on the set of finite trees labelled by natural numbers? (This holds, of course, by Kruskal's theorem if we replace $S$ with a finite set.)


Edit: Considering only well-quasi-orderings for the moment, one can also model this as follows: Given a tree $T$, we introduce for each label $c$ a new vertex $v\_{c}$, join it to all vertices of $T$ that have this label and forget about the labels. That makes the question almost an instance of the graph minor theorem (stating that the finite graphs are wqo under the minor relation) but for the fact that the embeddings must map extra vertices to extra vertices and tree vertices to tree vertices. This would follow if the graph minor theorem would continue to hold for graphs coloured with finitely many (in fact merely $2$) colours.



Equality-preserving embeddings of finite trees
Somewhat surprisingly, the answer is in fact **no**, even for paths. 


**Claim.** There is an infinite antichain of coloured paths under $\prec\_{ep}$.


**Proof.** Consider a path $P$ with $2k$ vertices, with vertices coloured from $[k]$. The first $k$ vertices of $P$ are coloured $1, \dots, k$, in that order, and the remaining $k$ vertices are coloured $1, \dots, k$, but in an arbitrary order. Thus, $P$ induces a permutation $\pi(P):[k] \to [k]$. Now given two such paths, $P$ and $Q$, observe that $P \prec\_{ep} Q$ if and only if $\pi(P) \leq \pi(Q)$, where $\leq$ is the containment relation on permutations. That is, $\pi\_1 \leq \pi\_2$ if we can obtain $\pi\_1$ from $\pi\_2$ by deleting elements of $\pi\_2$ and then renaming elements appropriately. 


In this [paper](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1n2), Spielman and Bóna exhibit an infinite antichain of permutations, so we are done modulo a slight lie. The slight lie is that a path may embed in another path with the opposite orientation. However, we can fix this using two extra colours red and blue. We add three red vertices to the beginning of a path and four blue vertices at the end of a path. This fixes the orientation, so we really are just working with the permutation order as claimed. 


This is joint with Luke Postle and Paul Wollan (possibly over beer). 


