◍wovepaper
SearchResearchersInstitutions
Sign in
math.COOct 1, 2018
13
citations (OpenAlex)
authors
  • Vida Dujmović
  • David Eppstein
  • Gwenaël Joret
  • Pat Morin
  • David R. Wood
institutions
  • Carleton University
  • Monash University
  • Université Libre de Bruxelles
  • University of California, Irvine
  • University of Ottawa
arXiv abstractPDF
paper

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

Cited by in corpus (5)

  • Clustered 3-Colouring Graphs of Bounded Degree
  • Notes on Graph Product Structure Theory
  • Separating layered treewidth and row treewidth
  • Surfaces have (asymptotic) dimension 2
  • Cubic Planar Graphs that cannot be Drawn on few Lines
◍wovepaper

Papers, researchers and institutions, woven together.

Explore
  • Search
  • Researchers
  • Institutions
Account
  • Library
  • Chat
Data
  • arXiv.org
  • Semantic Scholar
  • OpenAlex
  • Latest RSS
AboutContactPrivacyDevelopersllms.txtopenapi.json
Not affiliated with arXiv. Researcher data from Semantic Scholar (ODC-BY) and OpenAlex.