Djordje Vasić: Bounded tree-independence number versus (tw, ω)-boundedness

Bounded tree-independence number versus (tw, ω)-boundedness Djordje Vasić

Abstract: Graph width parameters measure structural complexity of graphs and are important tools for solving algorithmically hard problems on graphs. Treewidth is a graph width parameter that measures how similar the graph is to a tree. Another parameter, measuring how far a graph is from being chordal, is tree-independence number, introduced independently by Yolov in 2018 and Dallard, Milanič, and Štorgel in 2024. It is known that graphs with large cliques necessarily have large treewidth, and a graph class is said to be (tw, ω)-bounded if the converse is also true.

We study the relation of this property to boundedness of the tree-independence number. Dallard et al. showed that bounded tree-independence number is sufficient for (tw, ω)-boundedness, and conjectured that the converse holds. While Chudnovsky and Trotignon recently disproved this conjecture in general, it is still interesting to determine classes for which the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. We identify further families of graph classes where (tw, ω)-boundedness is equivalent to bounded tree-independence number and discuss (tw, ω)-boundedness in relation to induced minors.

The talk is based on joint works with Claire Hilaire, Martin Milanič, and Nicolas Trotignon.