The bounded-degree wall-or-line-wall induced-subgraph conjecture
The bounded-degree wall-or-line-wall induced-subgraph conjecture
Let be a graph, let and be positive integers, and let denote the -wall. A subdivision of a graph is obtained by replacing its edges by internally vertex-disjoint paths, and the line graph of a graph has one vertex for each edge, with adjacency when the corresponding edges share an endpoint. The wall-or-line-wall conjecture. For all , there exists such that every graph with maximum degree at most and treewidth more than contains a subdivision of or the line graph of a subdivision of as an induced subgraph. This conjecture was recently proved by a different method, so it is no longer open.
Sources & referencesView supporting material
Primary source
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi and Sophie Spirkl, “Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs”, arXiv:2203.06775 (2022).
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.