Metraipolis › archive › dc_f6b130e4ea86

Induced packing treewidth II. Excluding a clique or a biclique — arXiv:2609.21615

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21615
License (as archived)
CC0-1.0
Archived
2026-10-10T02:10:31.825Z
SHA-256 of the archived text
e0b7b6b4ec3c3ebba0776d83cbd533688293495217bab4c366da64eb2ef6a9cb
Stable URL of this page
https://metraipolis.com/documento/dc_f6b130e4ea86

How to cite

Induced packing treewidth II. Excluding a clique or a biclique — arXiv:2609.21615 — arXiv (en), https://arxiv.org/abs/2609.21615 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f6b130e4ea86 (Metraipolis archive dc_f6b130e4ea86, sha256 e0b7b6b4ec3c3ebba0776d83cbd533688293495217bab4c366da64eb2ef6a9cb)
BibTeX
@misc{dcf6b130e4ea86,
  title = {Induced packing treewidth II. Excluding a clique or a biclique — arXiv:2609.21615},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21615},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f6b130e4ea86; sha256 e0b7b6b4ec3c3ebba0776d83cbd533688293495217bab4c366da64eb2ef6a9cb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21615. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $H$, \emph{induced $H$-packing treewidth}, denoted by $\treepi_{H}$, is a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of $H$ intersecting that bag. This notion generalizes some previously studied parameters: when $H=P_1$, it is equivalent to tree-independence number, and when $H=P_2$, it is equivalent to induced matching treewidth. We prove the following: \begin{itemize}[itemsep=2mm,leftmargin=6mm] \item For all $a,t\in \mathbb{N}$, $K_{a,a}$-free graphs of bounded induced $P_t$-packing treewidth have bounded tree-independence number. This extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for $t=2$, and a result of Hajebi and Spirkl who showed that $(P_t,K_{a,a})$-free graphs have bounded tree-independence number. \item If $H$ is any fixed path or a star, then the class of graphs of bounded induced $H$-packing treewidth is $\chi$-bounded. Again, this extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for $H=P_2$. \item Finally, we study the relationship between induced packing treewidth and \emph{sim-width}, a width parameter based on branch decompositions. We show that, although \emph{sim-width} and induced $P_3$-packing treewidth are incomparable, graphs of bounded sim-width that exclude all \emph{$H$-obstructions}---certain graphs that force large induced $H$-packing treewidth---have bounded induced $H$-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}

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.21615 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T01:48:20.599Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).