Weak coloring numbers of minor-closed graph classes

2024/07/05 by Jędrzej Hodor, Hodor, Jędrzej, Hoang La +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2407.04588

openalex publication_date 2024/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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_r(G)= O(r^td(X)-1log r), which improves on the bound wcol_r(G) = O(r^g(td(X))) given by Dujmović 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.

Cited by

• Treedepth and 2-treedepth in graphs with no long induced paths

Related

• Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
• On the growth rate of minor-closed classes of graphs
• The grid-minor theorem revisited
• Graph coloring with no large monochromatic components
• Polynomial Bounds for the Grid-Minor Theorem