Minor-closed graph classes with bounded layered pathwidth
arXiv:1810.08314 · doi:10.1137/18M122162X
Abstract
We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.
References in corpus (8)
- Diameter and Treewidth in Minor-Closed Graph Families
- Layout of Graphs with Bounded Tree-Width
- Layered Separators in Minor-Closed Graph Classes with Applications
- Track Layouts, Layered Path Decompositions, and Leveled Planarity
- Clustered 3-Colouring Graphs of Bounded Degree
- Coloring planar graphs with three colors and no large monochromatic components
- Forcing a sparse minor
- Clustered Graph Coloring and Layered Treewidth