Unified spectral bounds on the chromatic number

DOI10.7151/DMGT.1835zbMATH Open1326.05080arXiv1210.7844OpenAlexW2964340196MaRDI QIDQ891325FDOQ891325

Authors: Clive Elphick, Pawel Wocjan 

Publication date: 17 November 2015

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

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 mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: chi >= 1 + mu_1 / (- mu_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.

Full work available at URL: https://arxiv.org/abs/1210.7844

Recommendations

• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Eigenvalues and chromatic number of a signed graph
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• Chromatic number and spectral radius
• A lower bound for the chromatic number of a graph

zbMATH Keywords

chromatic numbermajorization

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• The smallest eigenvalue of the signless Laplacian
• Chromatic number and spectral radius
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Title not available (Why is that?)
• Inequalities for the extreme eigenvalues of block-partitioned Hermitian matrices with applications to spectral graph theory

Cited In (11)

• More tales of Hoffman: bounds for the vector chromatic number of a graph
• Spectral lower bounds for the orthogonal and projective ranks of a graph
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• The high order spectrum of a graph and its applications in graph colouring and clique counting
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• A lower bound for the chromatic number of a graph
• Spectral lower bounds for the quantum chromatic number of a graph
• Distance Laplacian eigenvalues and chromatic number in graphs
• Eigenvalues and chromatic number of a signed graph
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship
• An inertial lower bound for the chromatic number of a graph

This page was built for publication: Unified spectral bounds on the chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q891325)