Polynomial χ-bound for path-induced rooted tree
Polynomial bounds for path-induced copy theorem (1.2) · arXiv:2302.08922
Status open high confidence
The question asks whether the main result of arXiv:2302.08922 (Theorem 1.2, which shows graphs with clique number at most t and large enough chromatic number contain a path-induced copy of any rooted tree (T,r)) can be strengthened to give a polynomial bound on the chromatic number. No follow-up resolving this question was found in the literature. Related work has made progress on polynomial chi-boundedness for specific induced-subgraph-free classes (P5-free graphs, box-intersection graphs), but the particular path-induced variant with bounded clique number remains unresolved.
Reviewer notes. The concept of path-induced copy was introduced in arXiv:2302.08922 itself. Theorem 1.2 gives a (non-polynomial) chi-bound for graphs excluding a path-induced copy of (T,r) with clique number at most t. The question is whether the bound can be made polynomial in t. Closely related active research includes polynomial Gyarfas-Sumner for P5-free graphs (arXiv:2512.24907) and for box-intersection graphs (arXiv:2407.16882), but neither addresses the path-induced variant. No follow-up directly resolving this question was found after four targeted searches.
Context
Scott, Seymour and Spirkl proved (Theorem 3.2) that excluding an induced tree and $K_{t,t}$ as a subgraph yields a polynomial bound $f(t)$ on average degree. The authors ask whether an analogous polynomial bound on chromatic number can be obtained for 1.2, which imposes the weaker hypothesis of bounded clique number at the cost of weakening the conclusion to a path-induced copy.
Notes. Question appears as rhetorical prose without a labelled environment; the sentence 'Is there any hope for a comparable strengthening of 1.2?' is the explicit formulation.
Source paper
A note on the Gyárfás-Sumner conjecture
Tung Nguyen, Alex Scott, Paul Seymour · 2023-02-17
https://arxiv.org/abs/2302.08922
PDF source