Gartland's breakability conjecture for wall-subdivision-free graphs

From papers

For a positive integer tt, let Lt\mathcal{L}_t denote the graph class used in the source. A graph is kk-breakable if, for every weight function w ⁣:V(G)[0,1]w\colon V(G)\to[0,1], it has a ww-balanced separator with a core of size strictly less than kk. A ww-balanced separator is a set whose removal leaves every component with weight at most 1/21/2, and a core for a set YY is a set XX such that YN[X]Y\subseteq N[X]. A subdivision of the t×tt\times t-wall is obtained by subdividing edges of that wall.

Gartland's conjecture. For every positive integer tt, there is an integer d=d(t)d=d(t) such that every Lt\mathcal{L}_t-free graph GG with no induced subgraph isomorphic to a subdivision of the t×tt\times t-wall is dd-breakable.

The conjecture concerns induced-subgraph obstructions to small tree independence number and is presented as support for a broader program involving walls and domination-based separators. The source states that its theorem on Mt\mathcal{M}_t^*-free graphs provides evidence, but does not specify a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov, Martin Milanič and Varun Sivashankar, “Tree independence number V. Walls and claws”, arXiv:2501.14658 (2025).

Solutions 0

No solutions have been posted yet.