Bounds on eigenvalues and chromatic numbers (Q1377497): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:07, 5 March 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
