Centered colorings and weak coloring numbers in minor-closed graph classes
This work addresses theoretical graph coloring problems for researchers in graph theory and algorithms, providing incremental improvements in bounds for specific graph classes.
The paper tackles the problem of determining maximum q-centered chromatic numbers and weak coloring numbers for minor-closed graph classes, achieving results within an O(q)-factor and constant factors for planar-excluding classes, with explicit improvements such as O(q^{t-1}) for K_t-minor-free graphs.
Let $\mathcal{C}$ be a proper minor-closed class of graphs. Given the minors excluded in $\mathcal{C}$, we determine the maximum $q$-centered chromatic number and the maximum $q$th weak coloring number of graphs in $\mathcal{C}$ within an $\mathcal{O}(q)$-factor. Moreover, when $\mathcal{C}$ excludes a planar graph, we determine it within a constant factor. Our results imply that the $q$-centered chromatic number of $K_t$-minor-free graphs is in $\mathcal{O}(q^{t-1})$, improving on the previously known $\mathcal{O}(q^{h(t)})$ bound with a large and non-explicit function $h$. We include similar bounds for another family of parameters, the fractional treedepth fragility rates. All our bounds are proved via the same general framework.