×

New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix. (English) Zbl 1295.05112

Summary: The purpose of this article is to improve existing lower bounds on the chromatic number \(\chi\). Let \(\mu_1,\ldots,\mu_n\) be the eigenvalues of the adjacency matrix sorted in non-increasing order.
First, we prove the lower bound \(\chi \geq 1 + \max_m\{\sum_{i=1}^m \mu_i / -\sum_{i=1}^m \mu_{n - i +1}\}\) for \(m=1,\ldots,n-1\). This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case \(m=1\). We provide several examples for which the new bound exceeds the Hoffman lower bound.
Second, we conjecture the lower bound \(\chi \geq 1 + s^+ / s^-\), where \(s^+\) and \(s^-\) are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the bound \(\chi \geq s^+/s^-\). We show that the conjectured lower bound is true for several families of graphs. We also performed various searches for a counter-example, but none was found. Our proofs rely on a new technique of considering a family of conjugates of the adjacency matrix, which add to the zero matrix, and use majorization of spectra of self-adjoint matrices.
We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected.
All these bounds are also valid when we replace the adjacency matrix \(A\) by \(W\ast A\) where \(W\) is an arbitrary self-adjoint matrix and \(\ast\) denotes the Schur product, that is, entrywise product of \(W\) and \(A\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

References:

[1] D. Avis, J. Hasegawa, Y. Kikuchi and Y. Sasaki, A quantum protocol to win the graph coloring game on all Hadamard graphs, Journal IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Volume E89-A Issue 5, pp. 1378-1381, 2006.
[2] E. R. Barnes, A lower bound for the chromatic number of a graph, Contemporary Mathematics, 275 (2001), 3-12. · Zbl 0982.05047
[3] R. Bhatia, Matrix analysis, Graduate text in mathematics, vol. 169, Springer
[4] Y. Bilu, Tales of Hoffman: Three extensions of Hoffman’s bound on the graph chromatic number, J. Combin, Theory, Ser. B, 96 (2006), 608-613. · Zbl 1094.05036
[5] B. Bollob´as, The chromatic number of random graphs, Combinatorica 8(1), 49-55, 1988. · Zbl 0666.05033
[6] B. Bollob´as and V. Nikiforov, Cliques and the spectral radius, J. Combin. Theory Ser. B 97 (2007), 859-865. the electronic journal of combinatorics 20(3) (2013), #P3916 · Zbl 1124.05058
[7] A. Brouwer and W. Haemers, Spectra of graphs, Universitext, Springer, 2012; http://www.win.tue.nl/ aeb/2WF02/spectra.pdf · Zbl 1231.05001
[8] P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, A. Winter, On the chromatic number of graph, The Electronic Journal of Combinatorics, 14, #R81, 2007. · Zbl 1182.05054
[9] D. Cvetkovic, Chromatic number and the spectrum of a graph, Publ. Inst. Math. (Beograd), 14(28) (1972), 25-38. · Zbl 0271.05111
[10] D, Cvetkovic, P. Rowlinson, and S. Smic, An introduction to the theory of graph spectra, London Mathematical Society Student Texts 75, Cambridge University Press, 2010 · Zbl 1211.05002
[11] C. Edwards and C. Elphick, Lower bounds for the clique and the chromatic number of a graph, Discrete Appl. Math. 5 (1983) 51-64. · Zbl 0535.05029
[12] C. Elphick, School Timetabling and Graph Colouring, PhD thesis (unpublished), University of Birmingham, UK, 1981.
[13] M. Gary and D. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, Freeman 1978.
[14] C. D. Godsil and M. W. Newman, Colouring an orthogonality graph, SIAM Journal on Discrete Mathematics 22(2) (2008), pp.–683-692. · Zbl 1167.05314
[15] C. Godsil, private correspondence, 2012.
[16] C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001. · Zbl 0968.05002
[17] G. Haynes, C. Park, A. Schaeffer, J. Webster, L. H. Mitchell, Orthogonal vector coloring, The Electronic Journal of Combinatorics, 17, #R55, 2010; http://www. combinatorics.org/ojs/index.php/eljc/article/view/v17i1r55/ · Zbl 1215.05066
[18] W. Haemers, Eigenvalue Techniques in Design and Graph Theory, Mathematisch Centrum, Amsterdam, 1979. · Zbl 0429.05012
[19] A. J. Hoffman, On eigenvalues and colourings of graphs, in: Graph Theory and its Applications, Academic Press, New York (1970), pp. 79-91. · Zbl 0221.05061
[20] J. Hastad, Clique is hard to approximate within n1−ε, Acta Math., 182:105-142, 1999. · Zbl 0989.68060
[21] B. R. Myers and R. Liu, A lower bound for the chromatic number of a graph, Networks 1 (1972), 273-277. · Zbl 0233.05105
[22] J. Jones, E. Knill, Efficient refocussing of one spin and two spin interactions for NMR quantum computation, J. Magn. Resonance 141 (1999), pp. 322-325
[23] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM 45(2), pp. 246-265, 1998. · Zbl 0904.68116
[24] L. Lov´asz, On the Shannon capacity of a graph, IEEE Trans. Inf. Th., 25(1) (1979), 1-7. · Zbl 0395.94021
[25] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002), 179-189. the electronic journal of combinatorics 20(3) (2013), #P3917 · Zbl 1005.05029
[26] V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl. 418, 257-268, 2006. · Zbl 1106.05065
[27] V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl. 426, 810814, 2007. · Zbl 1125.05063
[28] J. H. Smith, Some properties of the spectrum of a graph, pp. 403-406 in: Combinatorial Structures and their Applications, Proc. Conf. Calgary 1969, Gordon and Breach, New York, 1970. · Zbl 0249.05136
[29] G. W. Stewart and Ji-guang Sun, Matrix perturbation theory, Academic Press, 1990. · Zbl 0706.65013
[30] H. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B 40(1986), 113-117. · Zbl 0598.05047
[31] P. Wocjan, Computational power of Hamiltonians in quantum computing, Dissertation (unpublished), University of Karlsruhe, Germany, 2003; http://www.eecs.ucf.edu/ wocjan/dissertation.pdf the electronic journal of combinatorics 20(3) (2013), #P3918
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.