PreprintCC BY 4.0arXiv
Quantum n-coloring is undecidable for every n ≥ 3
Abstract
The quantum n-coloring problem, given graph G, asks whether there exists a perfect quantum strategy for the n-coloring game of G. Previously it was known that quantum n-coloring is undecidable only for n=3. We extend this to all n≥ 3 with one elementary reduction. Letting G'=(G□ K3)lor Kn−3, we show that G is quantum $3$-colorable if and only if G' is quantum n-colorable.
Related
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
- An undecidable problem in dynamics
- The Global Asymptotic Stability Problem for Linear MPC Is Undecidable
- Tiling 3D by Translates of a Single Polycube is Undecidable
BibTeX
@misc{kidmosefrederiksen2026quantum,
title = {{Quantum n-coloring is undecidable for every n $\ge$ 3}},
author = {Christian Bo Kidmose-Frederiksen and Alfred Leth Nielsen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05280},
eprint = {2610.05280},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05280},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum n-coloring is undecidable for every n ≥ 3
AU - Christian Bo Kidmose-Frederiksen
AU - Alfred Leth Nielsen
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05280
UR - https://arxiv.org/abs/2610.05280
AB - The quantum n-coloring problem, given graph G, asks whether there exists a perfect quantum strategy for the n-coloring game of G. Previously it was known that quantum n-coloring is undecidable only for n=3. We extend this to all n≥ 3 with one elementary reduction. Letting G'=(G□ K_3)lor K_n−3, we show that G is quantum $3$-colorable if and only if G' is quantum n-colorable.
ER -