Dallard et al.'s equivalence conjecture for tree-independence number

About 2 years old · traced to

Let G\mathcal{G} be a hereditary graph class. A graph class is (tw,ω)(\mathsf{tw},\omega)-bounded if its treewidth is bounded by a function of its clique number, and it has bounded tree-independence number if the tree-independence numbers of its graphs are uniformly bounded. Dallard et al.'s conjecture. The class G\mathcal{G} is (tw,ω)(\mathsf{tw},\omega)-bounded if and only if G\mathcal{G} has bounded tree-independence number. Bounded tree-independence number is known to imply (tw,ω)(\mathsf{tw},\omega)-boundedness, and the converse remains open in general; it is established for several important graph classes.

References

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.