Minor-Closed Graph Classes with Bounded Layered Pathwidth

Autor:	David R. Wood, Pat Morin, Gwenaël Joret, Vida Dujmović, David Eppstein
Rok vydání:	2020
Předmět:	FOS: Computer and information sciences Class (set theory) Discrete Mathematics (cs.DM) General Mathematics Minor (linear algebra) 0102 computer and information sciences Computer Science::Computational Complexity 01 natural sciences Combinatorics Pathwidth Computer Science::Discrete Mathematics FOS: Mathematics Graph minor Théorie des graphes Mathematics - Combinatorics 0101 mathematics Computer Science::Data Structures and Algorithms Mathematics Discrete mathematics 010102 general mathematics Graph Treewidth 010201 computation theory & mathematics Bounded function Combinatorics (math.CO) Computer Science - Discrete Mathematics
Zdroj:	SIAM journal on discrete mathematics, 34 (3
ISSN:	1095-7146 0895-4801
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5597d995adec1e8371ef6613f9b015a3 https://doi.org/10.1137/18m122162x Zobrazit plný text záznamu