Paperlane

no. 10 · Friday 6 November 2026

Bounds on the maximum denominator of fractional chromatic numbers

Xinbo Xu and Xuding Zhu

math.CO · v2 · 18 pp

Abstract

For a positive rational number $x=p/q$, where $p$ and $q$ are coprime positive integers, let $\operatorname{den}(x)=q$. For a positive integer $n$, let $\operatorname{sd}(n)=\max\{\operatorname{den}(χ_f(G)): |V(G)|=n\}$. Let $D(n)=2^{-n}(n+1)^{(n+1)/2}$. It was proved by Alon, Tuza and Voigt that $\operatorname{sd}(n)\le D(n)$. In this paper, we prove that $\operatorname{sd}(n)\le D(n)n^{-\frac12\log_2 n+\frac14\log_2\log_2 n+O(1)}$ for all sufficiently large $n$. For the lower bound on $\operatorname{sd}(n)$, it was recently proved by Bonamy, Hylasová, Kaiser and Sereni that $\limsup_{n\to\infty}\operatorname{sd}(n)^{1/n}\ge\sqrt{2}$. We prove that $\limsup_{n\to\infty}\operatorname{sd}(n)^{1/n}\ge 3^{1/3}>\sqrt{2}$.

comments
18 pages, 5 figures
fields
Combinatorics
pdf ↗ page arXiv:2610.41771 ↗