Chromatic number of Kₖ-free bounded treewidth graphs
Problem 3 · arXiv:1706.00337
Status open medium confidence
Problem 3 of Dvořák–Kawarabayashi (arXiv:1706.00337) asks for the exact maximum chromatic number of K_k-free graphs of tree-width at most t for k≥4, generalising their tight answer ⌈(t+3)/2⌉ for k=3. No paper fully resolving the question for any fixed k≥4 was found. A 2025 paper (Discrete Mathematics, ScienceDirect pii/S0012365X25001037) explicitly addresses the fractional version of the same question—the maximum fractional chromatic number of K_r-free partial t-trees—and may constitute partial progress, but the URL could not be verified (HTTP 403) so it is recorded only in the notes.
Reviewer notes. No verified follow-up paper that resolves Problem 3 (k≥4) was found. A 2025 paper titled 'Fractional colorings of partial t-trees with no large clique' (Discrete Mathematics, https://www.sciencedirect.com/science/article/pii/S0012365X25001037) was identified via web search as explicitly addressing the Dvořák–Kawarabayashi question for the fractional chromatic number, but ScienceDirect returned HTTP 403 and no arxiv preprint was located, so it cannot be cited with verified coordinates. If this paper proves tight bounds for the fractional chromatic number of K_r-free partial t-trees, the status might be upgraded to 'partial'. The lower bound g(t,k) > (1 − 1/2^{k−2})t from the source paper remains the best published lower bound known. The problem is open for k≥4 with high probability.
Context
Theorem 2 establishes that $g(t,k) > \bigl(1 - \frac{1}{2^{k-2}}\bigr)t$ for all $t \geq 0$ and $k \geq 2$, providing a lower bound on the maximum chromatic number. The case $k = 3$ (triangle-free) is completely resolved by Theorem 1, which gives the tight bound $\lceil(t+3)/2\rceil$, but the question remains open for $k \geq 4$.
Also stated in
Notes. PDF source — references section is garbled with a list of arXiv IDs; the problem statement itself is clearly legible
Source paper
Triangle-free graphs of tree-width t are ceil((t + 3)/2)-colorable
Zdeněk Dvořák, Ken-ichi Kawarabayashi · 2017-06-09
https://arxiv.org/abs/1706.00337
PDF source