A set $Q$ is well-quasi-ordered by a relation $\le$ if for every sequence $q_1,q_2,\ldots$ of elements of $Q$ there exist $i<j$ such that $q_i \le q_j$. In their Graph Minors series, Robertson and Seymour prove that graphs are well-quasi-ordered by the minor relation. This result, which is known as the Graph Minor Theorem, is considered one of the deepest results in graph theory and has several algorithmic applications.

Unfortunately, the same is not true for directed graphs and the relation of butterfly minor. In particular, we can easily identify two infinite antichains. We can then ask if classes of graphs that exclude these antichains are well-quasi-ordered by the butterfly minor relation. We prove that this is the case while at the same time providing a structure theorem for these graph classes.

This is joint work with Maria Chudnovsky, S-il Oum, Paul Seymour and Paul Wollan.