Unified Spectral Bounds On The Chromatic Number

Keywords

Chromatic number; Majorization

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: X ≥ 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 eigenval- ues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency ma- trix, and examples are cited for which the new bounds outperform known bounds.

Publication Date

1-1-2015

Publication Title

Discussiones Mathematicae - Graph Theory

Volume

35

Issue

4

Number of Pages

773-780

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.7151/dmgt.1835

Socpus ID

84945305284 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84945305284

This document is currently not available here.

Share

COinS