χ(G) bound via spectral radius for triangle-free graphs

Conjecture 1.7 · arXiv:2501.00567

arXiv Conjecture high confidence— first stated 2024-12-31

Authors: Anders Martinsson, Raphael Steiner

Status open high confidence

Martinsson and Steiner prove in Theorem 1.6 of arXiv:2501.00567 that every triangle-free graph G satisfies χ_f(G) ≤ (1+o(1))ρ(G)/ln ρ(G), where ρ(G) is the spectral radius. Conjecture 1.7 is the stronger statement that the same bound holds for the ordinary chromatic number χ(G). No subsequent paper resolving or disproving this conjecture was found in the indexed literature as of May 2026.

Reviewer notes. The paper proves the analogous bound for fractional chromatic number χ_f(G) (Theorem 1.6) as the main result; Conjecture 1.7 extends this to the ordinary chromatic number χ(G). Closely related follow-up work includes arXiv:2501.18238 (Martinsson, resolving Harris' conjecture: every triangle-free d-degenerate graph satisfies χ_f(G) ≤ O(d/ln d)) and arXiv:2601.15245 (coloring small locally sparse degenerate graphs with ordinary chromatic number bounds); neither directly addresses the spectral radius upper bound for χ(G) stated in Conjecture 1.7. No resolution of the conjecture was found.

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

Conjecture. Every triangle-free graph $G$ satisfies $\chi(G)\leq(1+o(1))\frac{\rho(G)}{\ln\rho(G)}$.

Context

Motivated by Harris's conjecture [27] that every triangle-free $d$-degenerate graph satisfies $\chi_f(G)\leq O(\frac{d}{\ln d})$ and by Molloy's bound $(1+o(1))\frac{\Delta(G)}{\ln\Delta(G)}$ in terms of the maximum degree. Since the spectral radius $\rho(G)$ is sandwiched between the degeneracy and the maximum degree, Theorem 1.6 of this paper (a new spectral upper bound on $\chi_f$) is presented as a first step toward interpolating between these two regimes.

Source paper

Local Shearer bound
Anders Martinsson, Raphael Steiner · 2024-12-31
https://arxiv.org/abs/2501.00567