Spectral lower bounds for the quantum chromatic number of a graph. II

DOI10.37236/9295MaRDI QIDQ2215470zbMATH OpenOpenAlexFDO

Authors Clive Elphick, Parisa Darbari, Pawel Wocjan

Publication date 13 December 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.07336

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

quantum informationspectral bounds

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Abstract: Hoffman proved that a graph $G$ with eigenvalues $m{u}_{1}geldotsgem{u}_n$ and chromatic number $chi(G)$ satisfies: [ chi ge 1 + kappa ] where $kappa$ is the smallest integer such that [ mu_1 + sum_{i=1}^{kappa} mu_{n+1-i} le 0. ] We strengthen this well known result by proving that $chi(G)$ can be replaced by the quantum chromatic number, $ch{i}_q(G)$, where for all graphs $ch{i}_q(G)lechi(G)$ and for some graphs $ch{i}_q(G)$ is significantly smaller than $chi(G)$. We also prove a similar result, and investigate implications of these inequalities for the quantum chromatic number of various classes of graphs, which improves many known results. For example, we demonstrate that the Kneser graph $K{G}_{p,2}$ has $ch{i}_q=chi=p-2$.

Recommendations

• Spectral lower bounds for the quantum chromatic number of a graph
• On the quantum chromatic number of a graph
• More tales of Hoffman: bounds for the vector chromatic number of a graph
• On the chromatic number of \(q\)-Kneser graphs
• Spectral lower bounds for the orthogonal and projective ranks of a graph

Cites work

• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• 5-chromatic strongly regular graphs
• Colouring the normalized Laplacian
• Interlacing eigenvalues and graphs
• On the quantum chromatic number of a graph
• Quantum homomorphisms
• Spectra of graphs
• Spectral lower bounds for the quantum chromatic number of a graph
• Spreads in strongly regular graphs

Cited in

(12)

• Estimating quantum chromatic numbers
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
• More tales of Hoffman: bounds for the vector chromatic number of a graph
• The cross-product conjecture for width two posets
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• On the quantum chromatic number of a graph
• Spectral bounds for the quantum chromatic number of quantum graphs
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• scientific article; zbMATH DE number 6744339 (Why is no real title available?)
• Quantum chromatic numbers via operator systems
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• Spectral lower bounds for the quantum chromatic number of a graph

This page was built for publication: Spectral lower bounds for the quantum chromatic number of a graph. II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2215470)