Minor-closed graph classes with bounded layered pathwidth

Vida Dujmovic, David Eppstein, Gwenael Joret, Pat Morin, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

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 generalizes 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.

Original languageEnglish
Pages (from-to)1693-1709
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number3
DOIs
Publication statusPublished - 30 Jul 2020

Keywords

  • Apex-forest
  • Graph minor
  • Layered pathwidth
  • Layered treewidth
  • Pathwidth
  • Treewidth

Cite this