PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 4 | 773-780
Tytuł artykułu

Unified Spectral Bounds on the Chromatic Number

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
35
Numer
4
Strony
773-780
Opis fizyczny
Daty
wydano
2015-11-01
otrzymano
2014-10-29
poprawiono
2015-03-10
zaakceptowano
2015-03-10
online
2015-11-10
Twórcy
autor
  • Department of Electrical Engineering and Computer Science University of Central Florida Orlando, FL 32816, USA, wocjan@eecs.ucf.edu
Bibliografia
  • [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] F.R.K. Chung, Spectral Graph Theory (CBMS Number 92, 1997).
  • [3] A.J. Hoffman, On eigenvalues and colourings of graphs, in: Graph Theory and its Applications, Academic Press, New York (1970) 79-91.
  • [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).
  • [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]
  • [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]
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1835
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.