Trotignon's bounded-treewidth conjecture for graphs excluding induced minors
Trotignon's bounded-treewidth conjecture for graphs excluding induced minors
For a graph , a string representation is an assignment of its vertices to curves in the plane such that two curves intersect if and only if the corresponding vertices are adjacent. An outerstring representation is a string representation in which all curves lie in the upper half-plane and each curve has exactly one endpoint on the -axis; graphs admitting such a representation are outerstring graphs. Let denote the wall and let denote the complete bipartite graph with parts of size .
Trotignon's conjecture. For all , there exists such that for every graph , if does not contain or as an induced minor, and every induced subgraph of that is an outerstring graph satisfies
then
The conjecture would give a uniform bound on the treewidth of graphs excluding these induced minors when all their outerstring induced subgraphs have bounded treewidth. It is refuted by the construction cited in the source.
Sources & referencesView supporting material
Primary source
Maria Chudnovsky, David Fischer, Sepehr Hajebi, Sophie Spirkl and Bartosz Walczak, “A simple layered-wheel-like construction”, arXiv:2507.06169 (2026).
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.