Chromatic number and spectral radius

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Let G be a graph, H be its chromatic number, L be the largest eigenvalue of its Laplacian, and M be the largest eigenvalue of its adjacency matrix. Then, complementing a well-known result of Hoffman, we show that L>=(H/(H-1))M

Keywords

Combinatorics, 05C50

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/129886

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0702723
 http://arxiv.org/abs/math/0702723

Collections

arXiv