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 , the maximum -th weak coloring number of -minor-free graphs is polynomial in . We determine this polynomial up to a factor of . Moreover, we tie the exponent of the polynomial to a structural property of , namely, -treedepth. As a result, for a fixed graph and an -minor-free graph , we show that , which improves on the bound given by Dujmović et al. (SODA, 2024), where is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum -th weak coloring number is in ), which is best possible.

生成讲解博客的中文版本

生成AI智能校验的中文版本