Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes
We show that, for all positive integers $t$ and $Δ$, there exists an integer $c$ such that, for every $K_t$-minor-free graph $G$ with maximum degree at most $Δ$, there exists a graph $H$ of treewidth at most $3$ and a path $P$ such that $G$ is isomorphic to a subgraph of the strong product $H\boxtimes P\boxtimes K_c$. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of $H$ independently of $t$ and $Δ$. As an immediate consequence we obtain a bound of $O(r^4)$ on the $r$-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.
Authors
- Vida Dujmović (ORCID: https://orcid.org/0000-0001-7250-0600)
- Pat Morin (ORCID: https://orcid.org/0000-0003-0471-4118)
- David R. Wood (ORCID: https://orcid.org/0000-0001-8866-3041)
- Robert Hickingbotham (ORCID: https://orcid.org/0009-0007-1817-8295)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24544
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint