Improved bounds for weak coloring numbers

Abstract

Weak coloring numbers generalize the notion of degeneracy of a graph. They were introduced by Kierstead \& Yang in the context of games on graphs. Recently, several connections have been uncovered between weak coloring numbers and various parameters studied in graph minor theory and its generalizations. In this note, we show that for every fixed $k\ge 1$, the maximum $r$-th weak coloring number of a graph with simple treewidth $k$ is $\Theta (r^{k-1}\log r)$. As a corollary, we improve the lower bound on the maximum $r$-th weak coloring number of planar graphs from $\Omega (r^2)$ to $\Omega (r^2\log r)$, and we obtain a tight bound of $\Theta (r\log r)$ for outerplanar graphs.

arXiv commentv3: revised following the referees' comments v2: minor changes (in particular, open problem 3 in v1 has already been solved)

References in corpus (10)

• Planar graphs have bounded queue-number
• Improper Colourings inspired by Hadwiger's Conjecture
• Improved bounds for centered colorings
• Polynomial expansion and sublinear separators
• Notes on Graph Product Structure Theory
• On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On distance r-dominating and 2r-independent sets in sparse graphs
• Uniform Orderings for Generalized Coloring Numbers
• Chromatic Numbers of Exact Distance Graphs

Cited by in corpus (1)

• Improved bounds for centered colorings