betaFeedback

WorksMathematics

Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes

Abstract

We show that, for all positive integers tt and ΔΔ, there exists an integer cc such that, for every KtK_t-minor-free graph GG with maximum degree at most ΔΔ, there exists a graph HH of treewidth at most 33 and a path PP such that GG is isomorphic to a subgraph of the strong product H⊠P⊠KcH\boxtimes P\boxtimes K_c. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of HH independently of tt and ΔΔ. As an immediate consequence we obtain a bound of O(r4)O(r^4) on the rr-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.

Paper details

vlnc:W_ebn25tjn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…