K. Wagner conjectured that if G1, G2, ... is any countable sequence of finite graphs, then there exist i, j with j > i ≥ 1 such that Gi is isomorphic to a minor of Gj. Kruskal proved this when G1, G2, ... are all trees. We prove a strengthening of Kruskal's result-Wagner's conjecture is true for all sequences in which G1 is planar. We hope to show in a future paper that Wagner's conjecture is true in general, and the results of this paper will be needed for that proof.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics