Unavoidability characterization via Kelly minors
Conjecture 6 · arXiv:2002.00496
Status open high confidence
Conjecture 6 from arXiv:2002.00496 proposes that a graph H is unavoidable if and only if H is a minor of some graph from Kelly's construction (equivalently, a minor of some graph obtained by gluing copies of K_4 along edges in a path-like way and subdividing all horizontal edges once). The 'only if' direction is established in the source paper itself: Kelly's construction yields posets with unbounded dimension whose cover graphs are planar with pathwidth 3, so every unavoidable graph must be a minor of some graph in this family. No follow-up paper proving or disproving the 'if' direction (the sufficiency claim) was found in five web searches covering the period 2021–2026.
Reviewer notes. No follow-up paper resolving this conjecture was found in five web searches (three WebSearch calls plus WebFetch of arXiv:2509.04026 and Semantic Scholar citations). The paper arXiv:2509.04026 ('Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars', 2025) studies related ladder-exclusion problems but focuses on induced minors and tree-independence number, not on this specific conjecture. The conjecture is recent (source paper posted 2021, published in Combinatorica 2022, Vol. 42(3)), so absence of follow-up evidence supports high-confidence open status.
Context
Kelly's construction gives posets with unbounded dimension whose cover graphs are planar and have pathwidth 3, implying every unavoidable graph must be a minor of some graph in this family. The authors conjecture this necessary condition is also sufficient, and note an equivalent reformulation: $H$ is unavoidable if and only if $H$ is a minor of some graph obtained by gluing copies of $K_4$ along edges in a path-like way and subdividing all horizontal edges once.
Source paper
Excluding a ladder
Tony Huynh, Gwenaël Joret, Piotr Micek, Michał T. Seweryn, Paul Wollan · 2021-04-06
https://arxiv.org/abs/2002.00496
PDF source