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

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) 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$.

Review text

Summary: \textit{A. J. Hoffman} [in: Graph Theory Appl., Proc. advanced Sem. Wisconsin, Madison 1969, 79--91 (1970; Zbl 0221.05061)] proved that a graph \(G\) with eigenvalues \(\mu_1 \geqslant \cdots \geqslant \mu_n\) and chromatic number \(\chi(G)\) satisfies: \[ \chi \geqslant 1 + \kappa,\] where \(\kappa\) is the smallest integer such that \[\mu_1 + \sum_{i=1}^{\kappa} \mu_{n+1-i} \leqslant 0.\] We strengthen this well known result by proving that \(\chi(G)\) can be replaced by the quantum chromatic number, \( \chi_q(G)\), where for all graphs \(\chi_q(G) \leqslant \chi(G)\) and for some graphs \(\chi_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 \(KG_{p,2}\) has \(\chi_q = \chi = p - 2\). \par For Part I see [\textit{C. Elphick} and \textit{P. Wocjan}, J. Comb. Theory, Ser. A 168, 338--347 (2019; Zbl 1421.05042)].

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

• 5-chromatic strongly regular graphs
• Colouring the normalized Laplacian
• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• 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

(14)

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

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)