p-Centered coloring bound for minor-free graphs

Status solved high confidence

Question 3 asks for a function $g$ such that every $X$-minor-free graph $G$ satisfies $\chi_p(G)\leqslant c\cdot p^{g(\operatorname{td}(X))}$. Hodor, La, Micek, and Rambaud (arXiv:2411.02122, 2024) prove that $K_t$-minor-free graphs satisfy $\chi_p(G)=O(p^{t-1})$; since tree-depth is minor-monotone, any graph $X$ with $\operatorname{td}(X)=h$ satisfies $|V(X)|\leqslant 2^h-1$, so $X$ is a minor of $K_{2^h-1}$, and hence every $X$-minor-free graph is $K_{2^h-1}$-minor-free, yielding $\chi_p(G)=O(p^{2^h-2})$ and answering Question 3 affirmatively. The same team further sharpens these bounds in arXiv:2603.13097 (2026), determining the maximum $q$-centered chromatic number of $K_t$-minor-free graphs within an $O(q)$-factor.

Cited literature (2)

• proof Centered colorings in minor-closed graph classes (2024)
  Jędrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud · arXiv preprint · arXiv:2411.02122

  Proves $\chi_p(G)=O(p^{t-1})$ for $K_t$-minor-free graphs; combined with the minor-monotonicity of tree-depth this gives a positive answer to Question 3 with $g(h)=2^h-2$; the paper also notes $O(p^{t-1}\log p)$ for general $X$-minor-free graphs with $\operatorname{td}(X)=t$, with a manuscript in preparation.

• proof Centered colorings and weak coloring numbers in minor-closed graph classes (2026)
  Jędrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud · arXiv preprint · arXiv:2603.13097

  Determines the maximum $q$-centered chromatic number of $K_t$-minor-free graphs within an $O(q)$-factor, establishing $O(q^{t-1})$ as essentially tight and providing refined bounds for the function $g$ in Question 3.

Reviewer notes. arXiv:2411.02122 is authored by Hodor, La, Micek, Rambaud — a subset of the Question 3 authors — confirming it is a direct follow-up. The key chain: tree-depth is minor-monotone, so td(X)=h implies |V(X)| ≤ 2^h−1, which implies X is a minor of K_{2^h−1}, which implies X-minor-free ⊆ K_{2^h−1}-minor-free; combined with O(p^{t-1}) for K_t-minor-free from 2411.02122, this gives g(h)=2^h−2. arXiv:2603.13097 (March 2026) appears to be the 'manuscript in preparation' referenced in 2411.02122.

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