Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Unified Spectral Bounds on the Chromatic Number

100%

Elphick C., Wocjan P.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 4

773-780

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Elphick C.

1 Wocjan P.

1 2015

Wyniki wyszukiwania

Unified Spectral Bounds on the Chromatic Number