Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 33 min ago
PreprintarXiv licencearXiv

Bounds on the maximum denominator of fractional chromatic numbers

  • Xinbo Xu
  • Xuding Zhu
Open at sourcePDFDOICite

Abstract

For a positive rational number x=p/q, where p and q are coprime positive integers, let den(x)=q. For a positive integer n, let sd(n)=max{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 sd(n)≤ D(n). In this paper, we prove that sd(n)≤ D(n)n−1/2log2 n+1/4log2log2 n+O(1) for all sufficiently large n. For the lower bound on sd(n), it was recently proved by Bonamy, Hylasová, Kaiser and Sereni that limsupn→∞sd(n)1/n≥√2. We prove that limsupn→∞sd(n)1/n≥ 31/3>√2.

Related

  1. Clique and chromatic numbers of graph powers: spectral bounds and anticodes
    Aida Abiad, Gabriel Coutinho, Hitesh Kumar +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Improved bounds on the b-chromatic number using the independence and chromatic numbers
    Manouchehr Zaker
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
    Aida Abiad, Stan van Hoesel, Valentin Michaux
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. New upper bounds for the chromatic numbers of Euclidean spaces
    Leonid Ivanov, Nadezhda Glushkova
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
    Meiqiao Zhang, Fengming Dong
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026bounds,
  title = {{Bounds on the maximum denominator of fractional chromatic numbers}},
  author = {Xinbo Xu and Xuding Zhu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41771},
  eprint = {2610.41771},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41771},
}
RIS
TY  - UNPB
TI  - Bounds on the maximum denominator of fractional chromatic numbers
AU  - Xinbo Xu
AU  - Xuding Zhu
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41771
UR  - https://arxiv.org/abs/2610.41771
AB  - For a positive rational number x=p/q, where p and q are coprime positive integers, let den(x)=q. For a positive integer n, let sd(n)=max{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 sd(n)≤ D(n). In this paper, we prove that sd(n)≤ D(n)n^−1/2log_2 n+1/4log_2log_2 n+O(1) for all sufficiently large n. For the lower bound on sd(n), it was recently proved by Bonamy, Hylasová, Kaiser and Sereni that limsup_n→∞sd(n)^1/n≥√2. We prove that limsup_n→∞sd(n)^1/n≥ 3^1/3>√2.
ER  -