Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
Mujin Choi, Sebastian Wiederrecht · 2025
Read Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars by Mujin Choi, Sebastian Wiederrecht (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-04026.txt.
Description
In a 2025 mathematics paper, Mujin Choi and one co-author examine graphs excluding a ladder as an induced minor and containing no induced star. A ladder joins two equal paths with rungs between matching vertices. Excluding such configurations defines well-behaved classes.
The main theorem: for every ladder size and star size, graphs avoiding both have bounded tree-independence number, a width measure combining tree decompositions with independence. Boundedness matters: many hard problems become tractable on such classes. The method sharpens several known results along the way. It improves an existing bound for graphs excluding wheels as induced minors. Graphs excluding thetas or prisms with long paths also get bounded tree-independence number, improving a result of Chudnovsky, Hajebi, and Trotignon. Finally, an induced Erdős-Pósa type result extends from long induced cycles to all subdivided-ladder minors. Graph theorists gain one argument covering several separate cases.
Catalog record
| CREATOR | Mujin Choi, Sebastian Wiederrecht |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-04026