The wall-subdivision formulation of the induced-grid conjecture
The wall-subdivision formulation of the induced-grid conjecture
Let be a positive integer and let be a hereditary graph class excluding . A subdivision of the elementary -wall is obtained by subdividing edges of the elementary -wall, and its line graph is formed by taking edges as vertices. The wall-subdivision formulation. The class has bounded tree-independence number if and only if there exists a positive integer such that excludes all subdivisions of the elementary -wall and their line graphs. This is stated as an equivalent induced-subgraph formulation of the induced-grid conjecture and remains open with that conjecture.
Sources & referencesView supporting material
Primary source
Clément Dallard, Matjaž Krnc, O-joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel and Sebastian Wiederrecht, “Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star”, arXiv:2402.11222 (2024).
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.