Skip to content
DraconiticResearch
Search Sources API
190,839 studies31 sourcesUpdated 55 min ago
PreprintarXiv licencearXiv

On the exact quantum chromatic number of generalized Johnson graphs

  • Gaojun Luo
  • Xiwang Cao
  • Shitao Li
  • Yang Li
Open at sourcePDFDOICite

Abstract

The quantum chromatic number is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with n, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.

Related

  1. The game chromatic number of generalized Mycielski graphs of paths and cycles
    Yushuang Mou, Qiang Sun, Chao Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  3. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Geometric triangle-free graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  5. Box-Delaunay graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{luo2026exact,
  title = {{On the exact quantum chromatic number of generalized Johnson graphs}},
  author = {Gaojun Luo and Xiwang Cao and Shitao Li and Yang Li},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.04677},
  eprint = {2609.04677},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.04677},
}
RIS
TY  - UNPB
TI  - On the exact quantum chromatic number of generalized Johnson graphs
AU  - Gaojun Luo
AU  - Xiwang Cao
AU  - Shitao Li
AU  - Yang Li
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.04677
UR  - https://arxiv.org/abs/2609.04677
AB  - The quantum chromatic number is a fundamental parameter in the study of nonlocal games, capturing the extent to which entanglement can improve performance in distributed tasks. In this paper, we investigate the quantum chromatic number of generalized Johnson graphs. By constructing modulus-one orthogonal representations, we obtain general upper bounds on their quantum chromatic numbers. We further analyze the smallest eigenvalue of these graphs. Combining the resulting Hoffman-type lower bounds with the upper bounds obtained from orthogonal representations, we determine the exact quantum chromatic numbers of two infinite families of generalized Johnson graphs. Finally, applying a forbidden-distance theorem for binary codes, we show that the classical chromatic numbers of these families grow exponentially with n, whereas their quantum chromatic numbers grow linearly. These families exhibit an exponential separation between the classical and quantum chromatic numbers.
ER  -