Robertson's conjecture on bounded Robertson chains
Robertson's conjecture on bounded Robertson chains
Let a Robertson chain of length be the graph obtained from a path of length 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 , graphs that do not contain the Robertson chain of length 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.