Spectral lower bounds for the quantum chromatic number of a graph

2018/05/22 by Paweł Wocjan, Pawel Wocjan, Wocjan, Pawel +2 · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Quantum Physics (quant-ph) #math.CO #quant-ph

paper · pdf · doi:10.48550/arxiv.1805.08334

Added funding info

openalex publication_date 2018/05/22 · arxiv created 2018/08/08 · arxiv updated 2018/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The quantum chromatic number, χ_q(G), of a graph G was originally defined as the minimal number of colors necessary in a quantum protocol in which two provers that cannot communicate with each other but share an entangled state can convince an interrogator with certainty that they have a coloring of the graph. We use an equivalent purely combinatorial definition of χ_q(G) to prove that many spectral lower bounds for the chromatic number, χ(G), are also lower bounds for χ_q(G). This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

Cited by

• Tales of Hoffman: from a distance
• Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph
• On the quantum chromatic number of Hamming and generalized Hadamard graphs

Related

• Spectral Lower Bounds for the Quantum Chromatic Number of a Graph -- Part II
• Spectral bounds for the quantum chromatic number of quantum graphs
• Eigenvalue bounds for the quantum chromatic number of graph powers
• On the Quantum Chromatic Numbers of Small Graphs
• On the quantum chromatic number of Hamming and generalized Hadamard graphs