We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph X, the maximum r-th weak coloring number of X-minor-free graphs is polynomial in r. We determine this polynomial up to a factor of O(r log r). Moreover, we tie the exponent of the polynomial to a structural property of X, namely, $2$-treedepth. As a result, for a fixed graph X and an X-minor-free graph G, we show that wcolᵣ(G)= O(rtd(X)-1log\ r), which improves on the bound wcolᵣ(G) = O(rg(td(X))) given by Dujmovi\'c et al. (SODA, 2024), where g is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum r-th weak coloring number is in O(r²log\ r), which is best possible.
No takes yet. Share an insight, caveat, or question.
Hodor et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: