Geodesic
Unified Spectral Bounds on the Chromatic Number
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 773-780

Voir la notice de l'article provenant de la source Library of Science

One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where μ1 and μn are respectively the maximum and minimum eigenvalues of the adjacency matrix: χ ≥ 1+μ1/−μn. We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.
Keywords: chromatic number, majorization 
@article{DMGT_2015_35_4_a13,
     author = {Elphick, Clive and Wocjan, Pawel},
     title = {Unified {Spectral} {Bounds} on the {Chromatic} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {773--780},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a13/}
}
TY  - JOUR
AU  - Elphick, Clive
AU  - Wocjan, Pawel
TI  - Unified Spectral Bounds on the Chromatic Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 773
EP  - 780
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a13/
LA  - en
ID  - DMGT_2015_35_4_a13
ER  - 
%0 Journal Article
%A Elphick, Clive
%A Wocjan, Pawel
%T Unified Spectral Bounds on the Chromatic Number
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 773-780
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a13/
%G en
%F DMGT_2015_35_4_a13
Elphick, Clive; Wocjan, Pawel. Unified Spectral Bounds on the Chromatic Number. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 773-780. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a13/