Chromatic number and spectral radius

Write mu(A) = mu(1)(A) >=...>= mu(min) (A) for the eigenvalUes of a Hermitian matrix A. Our main result is: Let A be a Hermitian matrix partitioned into r x r blocks so that all diagonal blocks are zero. Then for every real diagonal matrix B of the same size as A m(B - A) >= mu ( B + 1/r-1 A). Let G be a nonempty graph, X(G) be its chromatic number, A be its adjacency rnatrix, and L be its Laplacian. The above inequality implies the well-known result of Hoffman x(G) >= 1 + mu(A)/-mu(min)(A) and also, X(G) > 1 + mu(A)/mu(L) - mu(A) Equality holds in the latter inequality if and only if every two color classes of G induce a vertical bar mu(min)(A)vertical bar-regular subgraph. (C) 2007 Elsevier Inc. All rights reserved.