Note: this isn't a duplicate of this: Does the Robertson-Seymour theorem apply to vertex-labeled graphs?
One of equivalent definitions of graph minor is the following: $G_1$ is minor of $G_2$ if we can take some number of disjoint connected subgraphs of $G_2$ and "collapse" each of them (by using repeated edge contractions), and the resulting graph has $G_1$ as a subgraph (I might have missed some details there).
In the "Metamathematics of graph minor theorem" paper, labelled graph minor, with labels from some quasi order $(Q,\geq)$, is defined like above, except we add a condition: for vertex $v$ in $G_1$ with certain label $l$, there must be a vertex with a label $\geq l$ in a subset of $G_2$ collapse of which corresponds to $v$.
Labelled graph minor theorem says that, if $(Q,\geq)$ is well-quasi order, then so is the set of $Q$-labelled graphs under labelled graph minors.
I've seen this fact (or conjecture) stated in the aforementioned paper, but without explicitly saying that Robertson and Seymour have proved it.
My question is: is this statement true? (I might have forgotten some details, maybe $Q$ has to be finite, or does $(Q,\geq)$ has to be a linear ordering?)
3 years later: the question is open again, as I'm fairly sure the answer below is flawed (see my comment under that answer).
EDIT : WRONG ANSWER (see comment below)
The statement is true. $Q$ needs not to be finite. We just need that $(Q,\geq)$ is a well-quasi order.
Notation and recalls:
Let $\sqsubseteq$ be the minor ordering on graphs. We know that $\sqsubseteq$ is a well-quasi order by Robertson–Seymour theorem.
Let $\sqsubseteq_L$ be the minor ordering on labelled graphs.
Proof of: $\sqsubseteq_L$ is a well-quasi order (wqo).
Lets prove it by the absurd.
Let $(G_i)_{i\in\mathbb{N}}$ be a sequence of labelled graphs such that there is no increasing pairs $G_i\sqsubseteq_L G_j$ with $i<j$.
Since $\sqsubseteq$ is a wqo we can extract from $(G_i)_{i\in\mathbb{N}}$ a subsequence $(G'_i)_{i\in\mathbb{N}}$ such that $G'_i\sqsubseteq G'_{i+1}$ (if you see labelled graphs as normal graphs).
Notice that we also have $\forall i, G'_0\sqsubseteq G'_i$. Let $G'_0=(V,E,L)$ with $V=\{v_1,\dots,v_n\}$.
We define a sequence $(q_i^1)_{i\in\mathbb{N}}$ such that $q_i^1$ is a label in a subset of $G_i$ collapse of which results in $v_1$.
Since $\leq$ is a wqo there is an infinite subset $I_1\subseteq\mathbb{N}$ such that for all $i<j\in I_1$, $q_i^1\leq q_j^1$.
Patch: part 1: There are 2 cases, either there is such a sequence containing $0$ and we continue as before.
Or there are no such sequences containing $0$. For this case we remove from our sequence of graph all the graphs (a finite number) for which there is a vertex that collapse on $v_1$ and have a greater label. We then start over the procedure from the beginning. We cal this case a restart because of $v_1$ in $G_0$.
End of patch part 1
We can start again for the vertex $v_2$: We define a sequence $(q_i^2)_{i\in I_1}$ such that $q_i^1$ is a label in a subset of $G_i$ collapse of which results in $v_2$.
Since $\leq$ is a wqo there is an infinite subset $I_2\subseteq I_1$ such that for all $i<j\in I_2$, $q_i^2\leq q_j^2$.
We do that for all vertices. We end up with an infinite set $I_n$ such that for $i\in I_n$ we have $G'_0\sqsubseteq G'_i$ and for all vertex $v\in V$ there is a vertex with label $\geq$ in a subset of $G'_i$ collapse of which results in $v$. Hence $G'_0\sqsubseteq_L G'_i$. Contradiction with $(G_i)_{i\in\mathbb{N}}$ has no increasing pairs.
Hence $\sqsubseteq_L$ is a wqo.
I hope this is what you where looking for.
PATCH correction proof
Assume that there are only a finite number of restart. Then the proof works as before. The only problem is that we may need an infinite number of restart.
Assume that there are an infinite number of restart, we will show that this is in contradiction with $\geq$ a wqo.
Let $(R_i,n_i)_{i\mathbb{N}}$ be the sequence of restart.
Since there are an infinite number of restart, by the pigeon hole principle an infinite number of them are caused by vertices that would collapse on the same vertex $v$ of $G_0$. Call them $I_0$. For all this vertex $n_i$, with $i\in I_0$ we know that the label of $n_i$ is not greater than the label of $v$.
Take $l_0=min I_0$. Apply the same argument on $G_l$. and so on. Like this you get an infinite sequence of label with is an anti chain for $\geq$. Contradiction