The bounded-degree wall-or-line-wall induced-subgraph conjecture

Let GG be a graph, let kk and Δ\Delta be positive integers, and let Wk×kW_{k \times k} denote the (k×k)(k \times k)-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 k,Δ>0k, \Delta > 0, there exists c=c(k,Δ)c=c(k,\Delta) such that every graph with maximum degree at most Δ\Delta and treewidth more than cc contains a subdivision of Wk×kW_{k\times k} or the line graph of a subdivision of Wk×kW_{k \times k} 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

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.