Chromatic number and spectral radius (Q996333): Difference between revisions

The author studies the relationship between the chromatic number of a graph \(G\) and the spectral radius of its adjacency matrix. The main result of this work is the following: Let \(A\) be a Hermitian matrix partitioned into \(r \times r\) blocks so that all diagonal blocks are zero and \(\mu(A)=\mu_1(A) \geq \cdots \geq \mu_{\min}(A)\) are its eigenvalues. For every real diagonal matrix \(B\) of the same size as \(A\), we have \[ \mu(B-A) \geq \mu \left( B + \frac{1}{r-1}A \right). \] From this inequality the author deduces \[ \chi(G) \geq 1+ \frac{\mu(A)}{-\mu_{\min}(A)} \] and \[ \chi(G) \geq 1+ \frac{\mu(A)}{\mu(L)-\mu(A)}, \] where \(G\) is a nonempty graph, \(\chi(G)\) its chromatic number, \(A\) its adjacency matrix and \(L\) its Laplacian.