Lower Bound on the Maximum Denominator of Fractional Chromatic Numbers
What is the least integer $\text{sd}(n)$ such that every graph on $n$ vertices has fractional chromatic number $p /q$, where $p$ and $q$ are positive integers and $q \le \text{sd}(n)$? An upper bound on the determinants of Hadamard matrices implies that $\text{sd}(n)\le 2^{-n}(n+1)^{(n+1) /2}$. The only known lower bound on $\text{sd}(n)$ that is exponential in $n$ (asymptotically, roughly $1.346^n/\sqrt{\log n}$) was obtained using an iterated Mycielski construction [D. C. Fisher, J. Graph Theory 20 (1995), 403-409]. We improve on this bound by constructing a family of graphs which shows that $\text{sd}(n) \geq 2^{n/2}$.
Authors
- Tomáš Kaiser (ORCID: https://orcid.org/0000-0003-0448-0171)
- Jean‐Sébastien Sereni
- Karolína Hylasová
- Marthe Bonamy
Institutions
- Laboratoire des Sciences de l'Ingénieur, de l'Informatique et de l'Imagerie (FR)
- Laboratoire Bordelais de Recherche en Informatique (FR)
- University of West Bohemia in Pilsen (CZ)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2026-05-21
- DOI
- https://doi.org/10.37236/14524
- Primary Topic
- Image Retrieval and Classification Techniques
- Type
- article
- Field-Weighted Citation Impact
- 0.00