← 研踪 PaperTrailarXiv:2611.24544 · v1
Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes
首次提交 2026-11-18 22:50
版本更新 2026-11-18 22:50
雷达观测 2026-11-19 15:04
摘要
We show that, for all positive integers and , there exists an integer such that, for every -minor-free graph with maximum degree at most , there exists a graph of treewidth at most and a path such that is isomorphic to a subgraph of the strong product . This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of independently of and . As an immediate consequence we obtain a bound of on the -weak colouring number of bounded-degree graphs from any proper minor-closed graph class.
作者备注:28 pages, 4 figures, written by humans
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 22:50 · 最新观测版本
Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes
We show that, for all positive integers and , there exists an integer such that, for every -minor-free graph with maximum degree at most , there exists a graph of treewidth at most and a path such that is isomorphic to a subgraph of the strong product . This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of independently of and . As an immediate consequence we obtain a bound of on the -weak colouring number of bounded-degree graphs from any proper minor-closed graph class.
查看此版本解读 →查看此版本原文 ↗