Bounds on eigenvalues and chromatic numbers (Q1377497)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Bounds on eigenvalues and chromatic numbers |
scientific article; zbMATH DE number 1109491
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bounds on eigenvalues and chromatic numbers |
scientific article; zbMATH DE number 1109491 |
Statements
Bounds on eigenvalues and chromatic numbers (English)
0 references
7 September 1998
0 references
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.
0 references
eigenvalue
0 references
bound
0 references
chromatic number
0 references
