Polynomial τ_d-boundedness implies polynomial bound

Question: Polynomial bound analogue of Esperet's conjecture for $\tau_d$ · arXiv:2202.05557

arXiv Question high confidence— first stated 2023-01-10

Status open high confidence

The question asks whether $\tau_d$-boundedness in a hereditary class always implies polynomial $\tau_d$-boundedness, in analogy with Esperet's conjecture for $\omega(G)$. No paper resolving this question was found in a targeted web search. Importantly, the analogous Esperet conjecture for $\omega(G)$ was disproved by Bria\'nski, Davies, and Walczak ('Separating Polynomial $\chi$-Boundedness from $\chi$-Boundedness', Combinatorica 2024), providing relevant negative context, but their construction does not directly address the $\tau_d$ setting. The question remains open as of May 2026.

Reviewer notes. The analogous question for ω(G) (Esperet's original conjecture) was disproved by Briański, Davies and Walczak in 'Separating Polynomial χ-Boundedness from χ-Boundedness' (Combinatorica 2024); however their construction concerns clique-number-based boundedness and does not directly address τ_d. No paper specifically resolving the τ_d analogue was found. All three internal references were matched with fuzz ≤ 80 and address entirely different conjectures (Gyárfás–Sumner and Menger); none verified as relevant to this question.

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

Question. Let $\mathcal{C}$ be a hereditary class of graphs, and $d \geq 1$. Suppose that there is a function $f$ such that $\chi(G) \leq f(\tau_d(G))$ for each $G \in \mathcal{C}$. Can we always choose $f$ to be a polynomial? What if $d = 2$?

Context

This question, suggested by a referee and included by the authors, asks for an analogue of Esperet's conjecture in the setting of $\tau_d(G)$ in place of $\omega(G)$. It is motivated by the polynomial bounds proved in Theorem 1.6 and asks whether being $\tau_d$-bounded always implies being polynomially $\tau_d$-bounded.

Notes. Explicitly labelled as an open question suggested by a referee and incorporated into the paper.

Source paper

Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph
Alex Scott, Paul Seymour · 2023-01-10
https://arxiv.org/abs/2202.05557 PDF source