pipette
ESEspañol

Induced-Minor-Free Graphs Admit a Star-Based Separator of Size

Arnold Filtser, Nikolai Karol, Hung Le, Florian Lehner

Preprint

In the authors' words

Given an -induced-minor-free graph with vertices, we construct a balanced separator of consisting of star subgraphs. Our result is an induced-minor-free analog of the famous separator theorem for -minor-free graphs by Alon, Seymour, and Thomas [J. Amer. Math. Soc., 1990]. A key idea in our construction is a new decomposition of -induced-minor-free graphs, analogous to the cop decomposition for -minor-free graphs by Andreae [J. Combin. Theory Ser. B, 1986]. We also discuss several algorithmic applications of our result.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.