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

DOI10.37236/9295zbMATH Open1454.05041arXiv1910.07336OpenAlexW3111458298MaRDI QIDQ2215470FDOQ2215470

Authors: Clive Elphick, Parisa Darbari, Pawel Wocjan 

Publication date: 13 December 2020

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

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$.

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

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

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

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)

Cites Work

• Spectra of graphs
• On the quantum chromatic number of a graph
• Interlacing eigenvalues and graphs
• Quantum homomorphisms
• Spreads in strongly regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• 5-chromatic strongly regular graphs
• Spectral lower bounds for the quantum chromatic number of a graph
• Colouring the normalized Laplacian

Cited In (12)

• 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
• Title not available (Why is that?)
• 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
• Estimating quantum chromatic numbers

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)