Laplacian spectra and chromatic numbers of graphs (Q2769880)

The author considers the Laplacian \(L(G)\) of a locally finite, infinite, unoriented, connected graph \(G\) with a uniform bound. In the case of finite graphs, \(L(G)\) is just the usual Laplacian matrix of the graph. Let \(\lambda_{\infty}(G)\) denote the spectral radius of \(L(G)\) and let \(k(G)\) be the chromatic number of \(G\). The author shows that if \(G\) is finite, then \(k(G)\leq\lambda_{\infty}(G)\) with equality if and only if \(G\) is a complete graph, and when \(G\) is infinite (but locally finite with a uniform bound) then the strict inequality \(k(G)<\lambda_{\infty}(G)\) holds.