Planar graph r-th weak coloring number O(r² log r)

Conjecture 4 · arXiv:2102.10061

arXiv Conjecture high confidence— first stated 2022-03-25

Authors: Gwenaël Joret, Piotr Micek

Status partial high confidence

The conjecture that all planar graphs have r-th weak coloring numbers in O(r^2 \log r) remains open as of 2025. Hodor, La, Micek, and Rambaud (arXiv:2407.04588, SODA 2025) proved this bound for planar graphs of bounded treewidth and more generally for X-minor-free graphs via the 2-treedepth of X, but explicitly state that the exact growth rate for all planar graphs is unknown. The lower bound \Omega(r^2 \log r) from Joret--Micek and the upper bound O(r^3) for general planar graphs still leave a gap.

Cited literature (1)

partial Weak coloring numbers of minor-closed graph classes (2024)

Jędrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud · Proceedings of SODA 2025 / arXiv preprint · arXiv:2407.04588 · doi:10.1137/1.9781611978322.107

Proves O(r² log r) weak coloring numbers for planar graphs of bounded treewidth (Corollary 3), and more generally for X-minor-free graphs in terms of the 2-treedepth of X, but explicitly states that the exact growth rate for all planar graphs remains unknown.

Reviewer notes. Conjecture 4 from arXiv:2102.10061 is partially resolved: the O(r² log r) bound holds for bounded-treewidth planar graphs (Hodor, La, Micek, Rambaud 2024, SODA 2025), but the full conjecture for all planar graphs is explicitly stated as open in that paper.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Planar graphs have $r$-th weak coloring numbers in $O(r^2 \log r)$.

Context

The best known lower bound for the maximum $r$-th weak coloring number of planar graphs is $\Omega(r^2 \log r)$ (proved in this paper via Corollary 3) and the best upper bound is $O(r^3)$ due to Van den Heuvel, Ossona de Mendez, Quiroz, Rabinovich, and Siebertz. The authors find it particularly intriguing to close this gap and believe the lower bound gives the correct order of magnitude.

Notes. PDF source; the statement notation is sufficiently clear despite possible garbling. Section 4 (open problems) is absent from the extracted text, so additional open problems beyond Conjecture 4 may exist in the full paper.

Source paper

Improved bounds for weak coloring numbers
Gwenaël Joret, Piotr Micek · 2022-03-25
https://arxiv.org/abs/2102.10061 PDF source