EUVIMEDScopri EUVIMED
Crossref

Lower Bound on the Maximum Denominator of Fractional Chromatic Numbers

Marthe Bonamy, Karolína Hylasová, Tomáš Kaiser, Jean-Sébastien Sereni

The Electronic Journal of Combinatorics · 2026-05-22 · 33 (2)

DOI: 10.37236/14524 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-05-22. Written by Marthe Bonamy and 3 co-authors.

AbstractDati bibliograficiCiteRelated studies

Abstract (original language)

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}$.

Cite

APA

Bonamy, M., Hylasová, K., Kaiser, T., & Sereni, J. (2026). Lower Bound on the Maximum Denominator of Fractional Chromatic Numbers. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14524

Vancouver

Bonamy M, Hylasová K, Kaiser T, Sereni J. Lower Bound on the Maximum Denominator of Fractional Chromatic Numbers. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14524

BibTeX
@article{Bonamy2026,
  author = {Bonamy, Marthe and Hylasová, Karolína and Kaiser, Tomáš and Sereni, Jean-Sébastien},
  title = {Lower Bound on the Maximum Denominator of Fractional Chromatic Numbers},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {2},
  doi = {10.37236/14524}
}
Start for free →