Spectral lower bounds for the quantum chromatic number of a graph. (English) Zbl 1421.05042

Elphick, Clive; Wocjan, Pawel

J. Comb. Theory, Ser. A 168, 338-347 (2019).

Summary: The quantum chromatic number, \(\chi_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 \(\chi_q(G)\) to prove that many spectral lower bounds for the chromatic number, \(\chi(G)\), are also lower bounds for \(\chi_q(G)\). This is achieved using techniques from linear algebra called pinching and twirling. We illustrate our results with some examples.

MSC:

05C15	Coloring of graphs and hypergraphs
81P45	Quantum information, communication, networks (quantum-theoretic aspects)

Keywords:

graph coloring; chromatic number; spectral bounds; quantum information

References:

[1]	Ando, T.; Lin, M., Proof of a conjectured lower bound on the chromatic number of a graph, Linear Algebra Appl., 485, 15, 480-484 (2015) · Zbl 1322.05054
[2]	Bhatia, R., Matrix Analysis, Graduate Texts in Mathematics, vol. 169 (1997), Springer
[3]	Bhatia, R., Pinching, trimming, truncating, and averaging of matrices, Amer. Math. Monthly, 107, 7, 602-608 (2000) · Zbl 0984.15024
[4]	Bilu, Y., Tales of Hoffman: three extensions of Hoffman’s bound on the chromatic number, J. Combin. Theory Ser. B, 96, 4, 608-613 (2006) · Zbl 1094.05036
[5]	Cameron, P. J.; Montanaro, A.; Newman, M. W.; Severini, S.; Winter, A., On the quantum chromatic number of a graph, Electron. J. Combin., 14, Article R81 pp. (2007) · Zbl 1182.05054
[6]	Elphick, C.; Wocjan, P., Unified spectral bounds on the chromatic number, Discuss. Math. Graph Theory, 35, 773-780 (2015) · Zbl 1326.05080
[7]	Elphick, C.; Wocjan, P., An inertial lower bound for the chromatic number of a graph, Electron. J. Combin., 24, 1, Article P1.58 pp. (2017) · Zbl 1358.05104
[8]	Hoffman, A. J.; Howes, L., On eigenvalues and colorings of graphs, II, Ann. N.Y. Acad. Sci., 175, 1, 238-242 (1970) · Zbl 0227.05105
[9]	Karger, D.; Motwani, R.; Sudan, M., Approximate graph coloring by semidefinite programming, J. ACM, 45, 2, 246-265 (1998) · Zbl 0904.68116
[10]	Kolotilina, L. Y., Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory, J. Math. Sci., 176, 1, 44-56 (2011) · Zbl 1291.15050
[11]	de Lima, L. S.; Oliveira, C. S.; de Abreu, N. M.M.; Nikiforov, V., The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl., 435, 10, 2570-2584 (2011) · Zbl 1222.05180
[12]	Mančinska, L.; Roberson, D. E., Oddities of quantum colorings, Baltic J. Modern Comput., 4, 4, 846-859 (2016)
[13]	Mančinska, L.; Roberson, D. E., Quantum homomorphisms, J. Combin. Theory Ser. B, 118, 228-267 (2016) · Zbl 1332.05098
[14]	Nikiforov, V., Chromatic number and spectral radius, Linear Algebra Appl., 426, 2-3, 810-814 (2007) · Zbl 1125.05063
[15]	Watrous, J., The Theory of Quantum Information (2018), Cambridge University Press · Zbl 1393.81004
[16]	Wocjan, P.; Elphick, C., New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electron. J. Combin., 20, 3, Article P39 pp. (2013) · Zbl 1295.05112