Abstract:In this paper, we investigate the tree-independence number of graph classes that do not contain $K_{1,d}$ as an induced subgraph. Dallard et al. conjectured that for any positive integer $d$ and any planar graph $H$, the class of all $K_{1,d}$-free graphs without $H$ as an induced minor has bounded tree-independence number. Our main contribution towards this conjecture is showing that the conjecture holds for outerstring graphs. Additionally we give linear and quadratic bounds for the tree-independence number of various $K_{1,d}$-free graph classes, sharpening previous bounds. Finally, we bound the tree-independence number of $K_{2,d}$-free graphs additionally forbidding holes of length at least $5$.
From: Hidde Koerts [view email]
[v1]
Thu, 18 Jun 2026 14:05:30 UTC (831 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。