Agelos Georgakopoulos

On better-quasi-ordering under graph minors

The celebrated Graph Minor Theorem of Robertson & Seymour states that the finite graphs are well-quasi-ordered (WQO) under the minor relation. Well-known remaining open problems ask whether they are better-quasi-ordered (BQO), and whether the countably infinite graphs are WQO.

We connect these problems as follows: we prove that the finite graphs are WQO iff the countably infinite graphs with no infinite paths are WQO iff the latter are BQO. We provide further equivalent statements and side results. No prior knowledge of BQO theory or infinite graph theory is assumed.