Chromatic number and spectral radius (Q996333): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q1116414 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Juan Ramón Torregrosa Sánchez / rank | |||
Normal rank |
Revision as of 13:34, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic number and spectral radius |
scientific article |
Statements
Chromatic number and spectral radius (English)
0 references
14 September 2007
0 references
The author studies the relationship between the chromatic number of a graph \(G\) and the spectral radius of its adjacency matrix. The main result of this work is the following: Let \(A\) be a Hermitian matrix partitioned into \(r \times r\) blocks so that all diagonal blocks are zero and \(\mu(A)=\mu_1(A) \geq \cdots \geq \mu_{\min}(A)\) are its eigenvalues. For every real diagonal matrix \(B\) of the same size as \(A\), we have \[ \mu(B-A) \geq \mu \left( B + \frac{1}{r-1}A \right). \] From this inequality the author deduces \[ \chi(G) \geq 1+ \frac{\mu(A)}{-\mu_{\min}(A)} \] and \[ \chi(G) \geq 1+ \frac{\mu(A)}{\mu(L)-\mu(A)}, \] where \(G\) is a nonempty graph, \(\chi(G)\) its chromatic number, \(A\) its adjacency matrix and \(L\) its Laplacian.
0 references
Laplacian
0 references
largest eigenvalue
0 references
least eigenvalue
0 references
chromatic number
0 references