1210.7844 (Clive Elphick et al.)

New spectral bounds on the chromatic number combining eigenvalues of the
Laplacian and signless Laplacian    [PDF]

Clive Elphick, Pawel Wocjan

One of the best known results in spectral graph theory is a lower bound for the chromatic number due to Alan Hoffman, which uses the maximum and minimum eigenvalues of the adjacency matrix. Vladimir Nikiforov introduced hybrid bounds, with a lower bound for the chromatic number which uses the maximum eigenvalues of the adjacency and Laplacian matrices. His bound equals the Hoffman bound for regular graphs and is sometimes better for irregular graphs. In this paper we prove a bound which is never worse than the Nikiforov bound, using the maximum eigenvalues of the Laplacian and signless Laplacian matrices. We also use majorization to generalize this bound by encompassing all eigenvalues of these matrices. We compare the performance of these bounds for named and random graphs and derive several known bounds as corollaries of the new bound. Our proof relies on a technique of converting the adjacency matrix into the zero matrix by conjugating with q diagonal unitary matrices, where q equals the chromatic number. We also prove that the minimum number of diagonal unitary matrices that can be used to convert the adjacency matrix into the zero matrix is the normalized orthogonal rank, which can be strictly less than the chromatic number.

View original: http://arxiv.org/abs/1210.7844