Bounds on eigenvalues and chromatic numbers (Q1377497): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q1299997 |
Changed an Item |
||
| Property / reviewed by | |||
| Property / reviewed by: Dragos Cvetković / rank | |||
Normal rank | |||
Revision as of 18:18, 22 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bounds on eigenvalues and chromatic numbers |
scientific article |
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
