Chromatic number and spectral radius Original Research Article

Write μ(A)=μ1(A)greater-or-equal, slantedcdots, three dots, centeredgreater-or-equal, slantedμmin(A) for the eigenvalues of a Hermitian matrix A. Our main result is: Let A be a Hermitian matrix partitioned into r×r blocks so that all diagonal blocks are zero. Then for every real diagonal matrix B of the same size as AimageLet G be a nonempty graph, χ(G) be its chromatic number, A be its adjacency matrix, and L be its Laplacian. The above inequality implies the well-known result of Hoffmanimageand also,imageEquality holds in the latter inequality if and only if every two color classes of G induce a midμmin(A)mid-regular subgraph.