Open Problem Garden

Robertson and Seymour famously proved that the set of all finite graphs is well-quasi-ordered by the minor relation. More precisely, if we let be an infinite sequence of graphs, then there exist so that is a minor of . Their theory also gives us a rough structure theorem for the family of graphs without a fixed minor - a powerful tool for studying minors in finite graphs.

On the other hand, there are still large gaps in our understanding of minors of infinite graphs. For instance, while it is known that Wagner's conjecture does not hold in general for infinite graphs [T], it is possible that countably infinite graphs are well quasi-ordered.

The conjecture highlighted above is especially interesting, because (if true) it would imply the well quasi-ordering of finite graphs. Indeed, the well quasi-ordering of finite graphs is equivalent to the statement that every infinite set of finite graphs contains two distinct members, one of which is a minor of the other. This latter statement follows from the above conjecture, since we may form a single infinite graph from the disjoint union of the graphs in , and the proper self-minor of gives us a pair of graphs in with one a minor of the other.