pipette
ENEnglish

Induced packing treewidth II. Excluding a clique or a biclique

Amir Nikabadi, Pawe{\l} Rz\k{a}\.zewski

Preprint

En palabras de los autores

The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. For a graph , induced -packing treewidth, denoted by , is a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of intersecting that bag. This notion generalizes some previously studied parameters: when , it is equivalent to tree-independence number, and when , it is equivalent to induced matching treewidth. We prove the following: \begin{itemize}[itemsep=2mm,leftmargin=6mm] \item For all , -free graphs of bounded induced -packing treewidth have bounded tree-independence number. This extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for , and a result of Hajebi and Spirkl who showed that -free graphs have bounded tree-independence number. \item If is any fixed path or a star, then the class of graphs of bounded induced -packing treewidth is -bounded. Again, this extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for . \item Finally, we study the relationship between induced packing treewidth and sim-width, a width parameter based on branch decompositions. We show that, although sim-width and induced -packing treewidth are incomparable, graphs of bounded sim-width that exclude all -obstructions---certain graphs that force large induced -packing treewidth---have bounded induced -packing treewidth. This simultaneously generalizes and resolves questions posed by Abrishami et al. [SIAM J. Discrete Math., 2025] and Brettell et al. [European J. Comb., 2025]. \end{itemize}

Resultado principalLimitación que admiten los autores

Apareció: lunes, 21 de septiembre. arXiv. Preprint, todavía sin revisión por pares.