Unified Spectral Bounds on the Chromatic Number

Clive Elphick; Pawel Wocjan

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 773-780
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Clive Elphick, and Pawel Wocjan. "Unified Spectral Bounds on the Chromatic Number." Discussiones Mathematicae Graph Theory 35.4 (2015): 773-780. <http://eudml.org/doc/276021>.

@article{CliveElphick2015,
abstract = {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.},
author = {Clive Elphick, Pawel Wocjan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chromatic number; majorization},
language = {eng},
number = {4},
pages = {773-780},
title = {Unified Spectral Bounds on the Chromatic Number},
url = {http://eudml.org/doc/276021},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Clive Elphick
AU - Pawel Wocjan
TI - Unified Spectral Bounds on the Chromatic Number
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 773
EP - 780
AB - 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.
LA - eng
KW - chromatic number; majorization
UR - http://eudml.org/doc/276021
ER -

References

top
  1. [1] R. Bhatia, Matrix Analysis (Graduate Text in Mathematics, 169, Springer Verlag, New York, 1997). doi:10.1007/978-1-4612-0653-8[Crossref] 
  2. [2] F.R.K. Chung, Spectral Graph Theory (CBMS Number 92, 1997). Zbl0867.05046
  3. [3] A.J. Hoffman, On eigenvalues and colourings of graphs, in: Graph Theory and its Applications, Academic Press, New York (1970) 79-91. 
  4. [4] L. Yu. Kolotilina, Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory, J. Math. Sci. 176 (2011) 44-56 (translation of the paper originally published in Russian in Zapiski Nauchnykh Seminarov POMI 382 (2010) 82-103). Zbl1291.15050
  5. [5] L.S. de Lima, C.S. Oliveira, N.M.M. de Abreu and V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435 (2011) 2570-2584. doi:10.1016/j.laa.2011.03.059[WoS][Crossref] Zbl1222.05180
  6. [6] V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl. 426 (2007) 810-814. doi:10.1016/j.laa.2007.06.005[WoS][Crossref] Zbl1125.05063
  7. [7] P. Wocjan and C. Elphick, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electron. J. Combin. 20(3) (2013) P39. Zbl1295.05112

NotesEmbed ?

top

You must be logged in to post comments.