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

CREATORMujin Choi, Sebastian Wiederrecht
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-04026

Browse the full library · About the Tower of Babel