Robertson's labelled conjecture for topological minors

At least 5 years old · documented by

Let kk be a positive integer. Let G1,G2,…G_1,G_2,\ldots be graphs that do not contain a Robertson chain of length at least kk as a topological minor. Let QQ be a set equipped with a well-quasi-ordering ≤Q\leq_Q, and for each positive integer ii, let ϕi:V(Gi)→Q\phi_i:V(G_i)\rightarrow Q be a function. A homeomorphic embedding from a graph HH to a graph GG is an injective map on vertices together with paths or cycles assigned to edges, satisfying the usual disjointness and incidence conditions; write it as η:H↪G\eta:H\hookrightarrow G. Robertson's labelled conjecture. There exist integers j,j′j,j' with 1≤j<j′1\leq j<j' and a homeomorphic embedding η:Gj↪Gj′\eta:G_j\hookrightarrow G_{j'} such that

ϕj(v)≤Qϕj′(η(v))\phi_j(v)\leq_Q\phi_{j'}(\eta(v))

for every v∈V(Gj)v\in V(G_j). This is the labelled strengthening of Robertson's conjecture and is formulated using the equivalent homeomorphic-embedding characterization of topological minors; its resolution is not supplied here and remains open.

References

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.