List chromatic bound via sublinear clique condition

Question 1.5 · arXiv:1803.01051

arXiv Question high confidence— first stated 2018-03-02

Authors: Marthe Bonamy, Tom Kelly, Peter Nelson, Luke Postle

Status solved high confidence

Question 1.5 is answered affirmatively by the paper’s own main theorem (Theorem 1.1 of arXiv:1803.01051): for sufficiently large $\Delta$, every graph $G$ with maximum degree at most $\Delta$ and $\omega(G) \leq \omega$ satisfies $\chi_c(G) \leq 72\Delta\sqrt{\ln\omega/\ln\Delta}$. Setting $\omega = \Delta^{1/f(c)}$ gives $\chi_c(G) \leq 72\Delta/\sqrt{f(c)}$, which is at most $\Delta/c$ whenever $f(c) \geq (72c)^2$; since $\chi_\ell \leq \chi_c$, the function $f(c) = (72c)^2$ witnesses a positive answer to the question. No subsequent paper is needed to resolve it.

Reviewer notes. Question 1.5 is posed in the introduction of 1803.01051 to motivate the paper’s main result, and that same result resolves it positively. The Kelly PhD thesis (University of Waterloo) explicitly records the corollary: if $\omega(G) \leq \Delta^{1/(72c)^2}$ and $\Delta$ is sufficiently large, then $\chi_c(G) \leq \Delta/c$. The internal reference 2012.13916 concerns a different notion ($\chi’_c$ for edge colouring) and is not relevant to this conjecture.

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

Question. Does there exist a function $f : \mathbb{R} \to \mathbb{R}$ such that, for every $c > 1$ and every graph $G$ of maximum degree at most $\Delta$ with no clique of size greater than $\Delta^{1/f(c)}$, we have $\chi_\ell(G) \leq \Delta/c$?

Context

A linear improvement on the greedy bound for graphs without large cliques was notably missing before this paper. Molloy's Theorem 1.2 gives a bound of $200\omega\,\frac{\Delta\ln\ln\Delta}{\ln\Delta}$, and Spencer's Ramsey-theory result shows the bound cannot be improved when $\omega = \Omega(\Delta^{1/2})$, motivating the question of whether a sublinear clique-number condition suffices for a $\Delta/c$ bound on $\chi_\ell$.

Notes. The paper answers Question 1.5 in the affirmative via Theorem 1.6, with $f(c) = (72c)^2$ sufficing for large enough $\Delta$.

Source paper

Bounding $χ$ by a fraction of $Δ$ for graphs without large cliques
Marthe Bonamy, Tom Kelly, Peter Nelson, Luke Postle · 2018-03-02
https://arxiv.org/abs/1803.01051 PDF source