Quantum independence and chromatic numbers

2024/01/29 by Godsil, Chris, Sobchuk, Mariia · 1 citation
Chemistry · #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #History and advancements in chemistry #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2401.16518

openalex created_date 2019/10/18 · openalex publication_date 2024/01/29 · openalex updated_date 2026/07/28

Abstract

We construct a new graph on 120 vertices whose quantum and classical independence numbers are different. At the same time, we construct an infinite family of graphs whose quantum chromatic numbers are smaller than the classical chromatic numbers. Furthermore, we discover the relation to Kochen-Specker sets that characterizes quantum cocliques that are strictly bigger than classical ones. Finally, we prove that for graphs with independence number is two, quantum and classical independence numbers coincide.

Cited by

• Tales of Hoffman: from a distance

Related

• No Quantum Brooks' Theorem
• Quantum Mycielski Graphs
• On the Quantum Chromatic Numbers of Small Graphs
• An inertial upper bound for the quantum independence number of a graph
• Spectral upper bound on the quantum k-independence number of a graph