WorksMathematics
On (Pathwidth, Clique)-boundedness
Abstract
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.