Robertson's conjecture on bounded Robertson chains

Let a Robertson chain of length kk be the graph obtained from a path of length kk by duplicating each edge. A graph contains another graph as a topological minor if the latter can be obtained from a subgraph of the former by repeatedly contracting edges incident with vertices of degree two. Robertson's conjecture. For every positive integer kk, graphs that do not contain the Robertson chain of length kk as a topological minor are well-quasi-ordered by the topological minor relation. This conjecture identifies the known obstruction to well-quasi-ordering graphs under topological containment and is the main objective of the paper; the bounded tree-width case is proved here, while the general conjecture remains open.

Sources & referencesView supporting material

Primary source

Chun-Hung Liu and Robin Thomas, “Robertson's conjecture I. Well-quasi-ordering bounded tree-width graphs by the topological minor relation”, arXiv:2006.00192 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.