WorksMathematics
Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes
Abstract
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.