Induced Forest Minor Theorem for Graphs Without an Induced Star

@misc{hickingbotham2026induced,
  title = {{Induced Forest Minor Theorem for Graphs Without an Induced Star}},
  author = {Robert Hickingbotham and Gwenaël Joret},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.10406},
  eprint = {2609.10406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10406},
}

TY  - UNPB
TI  - Induced Forest Minor Theorem for Graphs Without an Induced Star
AU  - Robert Hickingbotham
AU  - Gwenaël Joret
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.10406
UR  - https://arxiv.org/abs/2609.10406
AB  - Motivated by recent work on tree independence number, we study the path independence number of a graph G: the minimum integer k such that there is a path decomposition of G where each bag induces a graph with independence number at most k. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milani{č}, Munaro, Štorgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest H and integer t, there is a polynomial-time algorithm to test whether a K_1,t-induced-subgraph-free graph contains H as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on K_1,t-induced-subgraph-free graphs that exclude H as an induced minor.
ER  -