Unified spectral bounds on the chromatic number. (English) Zbl 1326.05080

Elphick, Clive; Wocjan, Pawel

Discuss. Math., Graph Theory 35, No. 4, 773-780 (2015).

Summary: One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to A. Hoffman [“On eigenvalues and colourings of graphs”, in: B. Harris (ed.), Graph theory and its applications. Proceedings of an advanced seminar conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, October 13–15, 1969. New York-London: Academic Press. 79–91 (1970)], where \(\mu_1\) and \(\mu_n\) are respectively the maximum and minimum eigenvalues of the adjacency matrix: \(\chi\geq 1+\mu_1/-\mu_n\). We recently generalised this bound to include all eigenvalues of the adjacency matrix.{ } In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.

MSC:

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

Keywords:

chromatic number; majorization

Citations:

Zbl 0206.26002

References:

[1]	R. Bhatia, Matrix Analysis (Graduate Text in Mathematics, 169, Springer Verlag, New York, 1997). doi:10.1007/978-1-4612-0653-8;
[2]	F.R.K. Chung, Spectral Graph Theory (CBMS Number 92, 1997).; · Zbl 0867.05046
[3]	A.J. Hoffman, On eigenvalues and colourings of graphs, in: Graph Theory and its Applications, Academic Press, New York (1970) 79-91.; · Zbl 0221.05061
[4]	L. Yu. Kolotilina, Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory, J. Math. Sci. 176 (2011) 44-56 (translation of the paper originally published in Russian in Zapiski Nauchnykh Seminarov POMI 382 (2010) 82-103).; · Zbl 1291.15050
[5]	L.S. de Lima, C.S. Oliveira, N.M.M. de Abreu and V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435 (2011) 2570-2584. doi:10.1016/j.laa.2011.03.059; · Zbl 1222.05180
[6]	V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl. 426 (2007) 810-814. doi:10.1016/j.laa.2007.06.005; · Zbl 1125.05063
[7]	P. Wocjan and C. Elphick, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electron. J. Combin. 20(3) (2013) P39.; · Zbl 1295.05112