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 $\pi$ 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, 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).

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, 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).