← 研踪 PaperTrailarXiv:2611.22552 · v1
On (Pathwidth, Clique)-boundedness
首次提交 2026-11-17 18:42
版本更新 2026-11-17 18:42
雷达观测 2026-11-18 11:33
摘要
We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor as an induced minor, where $\B_ρ$ is the complete binary tree of height and the bound depends only on and . We then obtain an asymptotically sharp bound on the path-independence number of -vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest and every , there is a constant such that every graph with no induced theta or -long prism and no induced subgraph isomorphic to satisfies tree-independence number at most . This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer , we characterize the forests for which excluding as an induced minor and as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with excluded as a subgraph.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 18:42 · 最新观测版本
On (Pathwidth, Clique)-boundedness
We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor as an induced minor, where $\B_ρ$ is the complete binary tree of height and the bound depends only on and . We then obtain an asymptotically sharp bound on the path-independence number of -vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest and every , there is a constant such that every graph with no induced theta or -long prism and no induced subgraph isomorphic to satisfies tree-independence number at most . This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer , we characterize the forests for which excluding as an induced minor and as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with excluded as a subgraph.
查看此版本解读 →查看此版本原文 ↗