Quickly excluding an apex-forest

2024/04/26 by Hodor, Jędrzej, La, Hoang, Micek, Piotr +1 · 3 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2404.17306

Abstract

We give a short proof that for every apex-forest X on at least two vertices, graphs excluding X as a minor have layered pathwidth at most 2|V(X)|-3. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs.

Cited by

• Erdős-Pósa property of rooted tree minors
• Treedepth and 2-treedepth in graphs with no long induced paths
• Colorful Minors

Related

• Excluding a Forest Induced Minor
• Tree-width of a graph excluding an apex-forest or a wheel as a minor
• Erdős-Pósa property of rooted tree minors
• Polynomial Bounds in the Apex Minor Theorem
• A shorter proof of the path-width theorem