Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth
The pathwidth of a graph $G$ is the smallest $w\\in \\mathbb{N}$ such that $G$ can be constructed from a sequence of graphs, each on at most $w+1$ vertices, by gluing them together in a linear fashion. We provide a full classification of the unavoidable induced subgraphs of graphs with large pathwidth.
Authors
- Sophie Spirkl (ORCID: https://orcid.org/0000-0002-2536-5618)
- Maria Chudnovsky (ORCID: https://orcid.org/0000-0002-8920-4944)
- Sepehr Hajebi (ORCID: https://orcid.org/0000-0002-4551-7834)
Publication Details
- Journal
- Advances in Combinatorics
- Published
- 2026-09-21
- DOI
- https://doi.org/10.19086/aic.2026.8
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Government of Ontario
- Natural Sciences and Engineering Research Council of Canada
- Engineering and Physical Sciences Research Council
- Air Force Office of Scientific Research