Gartland's breakability conjecture for wall-subdivision-free graphs
Gartland's breakability conjecture for wall-subdivision-free graphs
For a positive integer , let denote the graph class used in the source. A graph is -breakable if, for every weight function , it has a -balanced separator with a core of size strictly less than . A -balanced separator is a set whose removal leaves every component with weight at most , and a core for a set is a set such that . A subdivision of the -wall is obtained by subdividing edges of that wall.
Gartland's conjecture. For every positive integer , there is an integer such that every -free graph with no induced subgraph isomorphic to a subdivision of the -wall is -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 -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
Sign in to submit a solution.
No solutions have been posted yet.