Iskanje po repozitoriju

Opis: We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with respect to different measures of a tree decomposition T of a graph G: for tree-independence number, the measure is the maximum size of an independent set in G included in some bag of T, while for the induced matching treewidth, the measure is the maximum size of an induced matching in G such that some bag of T contains at least one endpoint of every edge of the matching. While the induced matching treewidth of any graph is bounded from above by its tree-independence number, the family of complete bipartite graphs shows that small induced matching treewidth does not imply small tree-independence number. On the other hand, Abrishami, Briański, Czyżewska, McCarty, Milanič, Rzążewski, and Walczak [SIAM Journal on Discrete Mathematics, 2025] showed that, if a fixed biclique K_{t,t} is excluded as an induced subghraph, then the tree-independence number is bounded from above by some function of the induced matching treewidth. The function resulting from their proof is exponential even for fixed t, as it relies on multiple applications of Ramsey’s theorem. In this note we show, using the Kövári-Sós-Turán theorem, that for any class of K_{t,t}-free graphs, the two parameters are in fact polynomially related.
Ključne besede: tree-independence number, induced matching treewidth, induced biclique, Kövári-Sós-Turán theorem
Objavljeno v RUP: 17.09.2026; Ogledov: 280; Prenosov: 6
Celotno besedilo (471,21 KB)
Gradivo ima več datotek! Več...