2025/10/22 by Agelos Georgakopoulos, Georgakopoulos, Agelos
Computer Science · Mathematics · #05C63 #05C83 #06A07 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.2510.19285
openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
In the aftermath of the Robertson--Seymour Graph Minor Theorem, Thomas conjectured that the countable graphs are well-quasi-ordered under the minor relation. We prove that this conjecture, when restricted to graphs with no infinite paths (rays), is equivalent to the statement that the finite graphs are better-quasi-ordered, another well-known open problem. Even more, we prove that the latter implies that the countable rayless graphs are better-quasi-ordered. We prove several other statements to be equivalent to the above, one of which being that the rayless countable graphs of rank α can be decomposed into exactly ℵ0 minor-twin classes for every ordinal α<ω1. By restricting the latter statement to trees, and combining it with Nash-Williams' theorem that the infinite trees are well-quasi-ordered, we deduce as a side result that a minor-closed family of N-labelled rayless forests is Borel -- in the Tychonoff product topology -- if and only if it does not contain all rayless forests. As another side-result, we prove Seymour's self-minor conjecture for rayless graphs of any cardinality.