The induced-grid conjecture for tree-independence number

Let dd be a positive integer and let C\mathcal{C} be a hereditary graph class excluding K1,dK_{1,d}. Define its induced minor closure by

C^={HH is an induced minor of some GC}.\widehat{\mathcal{C}}=\{H\mid H\text{ is an induced minor of some }G\in\mathcal{C}\}.

The induced-grid conjecture. The class C\mathcal{C} has bounded tree-independence number if and only if C^\widehat{\mathcal{C}} does not contain all planar graphs. This is proposed as a generalization of the induced Grid-Minor Theorem from bounded-degree graphs to hereditary classes excluding a star; the source presents it as open.

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

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.