Bounds on eigenvalues and chromatic numbers (Q1377497): Difference between revisions

The author proves the inequality \(\rho(G)\leq \sqrt{T(G)}\) where \(\rho(G)\) is the largest eigenvalue of (the adjacency matrix of) a graph \(G\) and \(T(G)\) is the maximum sum of degrees of vertices adjacent to a vertex in \(G\). Equality holds if and only if \(G\) is regular or semiregular bipartite. The corresponding upper bound for the chromatic number is derived. The result also implies the Brooks theorem.