Polynomial χ-bound via τ_d for path-free graphs

Question: Extending Theorem 1.6 to paths · arXiv:2202.05557

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

Status partial medium confidence

The conjecture asks whether polynomial bounds chi(G) <= f(tau_d(G)) hold for every path-free graph G, extending Theorem 1.6 (proved for trees of radius two) to paths. A direct successor in the series, 'Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph' by Nguyen (Journal of Graph Theory, 2024, DOI 10.1002/jgt.23129), bears a title that mirrors the structure of the source paper and appears to address exactly this question; however, the full theorem statement could not be verified due to paywall access. The internal corpus references (arXiv:2409.09397, arXiv:2409.09400) concern Gyarfas-Sumner stable-set bounds for forest-free graphs and do not address this specific conjecture about tau_d and chromatic number.

Cited literature (1)

partial Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph (2024)

Nguyen · Journal of Graph Theory · doi:10.1002/jgt.23129

Title mirrors paper V and addresses polynomial chi-bounds for path-free graphs excluding a complete multipartite graph (the structure captured by tau_d); exact theorem scope unverified due to paywall (HTTP 402 on fetch).

Reviewer notes. Part VIII of the 'Polynomial bounds for chromatic number' series ('Excluding a path and a complete multipartite graph', Nguyen 2024, JGT, DOI 10.1002/jgt.23129) is the strongest candidate for a resolution of this conjecture: its title exactly parallels paper V's title with 'path' replacing 'tree of radius two', suggesting it proves chi(G) <= poly(tau_d(G)) for path-free graphs. Status is 'partial' rather than 'solved' because the Wiley page returned HTTP 402 (paywall) and the exact theorem statement could not be read. Part VI (arXiv:2202.10412) treats the four-vertex path in the clique-number chi-bounded framework (not tau_d) and remains limited to specific short paths. The three internal corpus references all concern different conjectures (Gyarfas-Sumner stable sets or coarse Menger) and are not relevant here.

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

Question. Is it true that if $H$ is a path, then for every integer $d \geq 1$, there is a polynomial $f$ such that $\chi(G) \leq f(\tau_d(G))$ for every $H$-free graph $G$?

Context

This question, suggested by a referee and included by the authors, asks whether the main result (Theorem 1.6 for trees of radius two) can be extended to paths—another prominent family of forests for which polynomial bounds in terms of $\tau_2(G)$ are already known (via results of Bonamy et al. and Scott-Seymour-Spirkl).

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