New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix

zbMATH Open1295.05112arXiv1209.3190MaRDI QIDQ396873FDOQ396873

Authors: Clive Elphick, Pawel Wocjan 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The purpose of this article is to improve existing lower bounds on the chromatic number chi. Let mu_1,...,mu_n be the eigenvalues of the adjacency matrix sorted in non-increasing order. First, we prove the lower bound chi >= 1 + max_m {sum_{i=1}^m mu_i / - sum_{i=1}^m mu_{n-i+1}} for m=1,...,n-1. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case $m=1$. We provide several examples for which the new bound exceeds the {sc Hoffman} lower bound. Second, we conjecture the lower bound chi >= 1 + S^+ / S^-, where S^+ and S^- are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the weaker bound chi >= S^+/S^-. We show that the conjectured lower bound is tight for several families of graphs. We also performed various searches for a counter-example, but none was found. Our proofs rely on a new technique of converting the adjacency matrix into the zero matrix by conjugating with unitary matrices and use majorization of spectra of self-adjoint matrices. We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected. All these bounds are also valid when we replace the adjacency matrix A by W * A where W is an arbitrary self-adjoint matrix and * denotes the Schur product, that is, entrywise product of W and A.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Unified spectral bounds on the chromatic number
• A lower bound for the chromatic number of a graph
• Chromatic number and spectral radius
• Eigenvalues and chromatic number of a signed graph
• More tales of Hoffman: bounds for the vector chromatic number of a graph

zbMATH Keywords

spectral graph theorychromatic numberHoffman bound

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?)
• Some Inequalities for the Largest Eigenvalue of a Graph
• Spectra of graphs
• On the quantum chromatic number of a graph
• Title not available (Why is that?)
• An introduction to the theory of graph spectra
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Title not available (Why is that?)
• Chromatic number and spectral radius
• The chromatic number of random graphs
• Lower bounds for the clique and the chromatic numbers of a graph
• Title not available (Why is that?)
• Cliques and the spectral radius
• Walks and the spectral radius of graphs
• Spectral bounds for the clique and independence numbers of graphs
• Coloring an Orthogonality Graph
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• A lower bound for the chromatic number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• A lower bound on the chromatic number of a graph
• Orthogonal vector coloring

Cited In (23)

• Unified spectral bounds on the chromatic number
• A Brualdi-Hoffman-Turán problem on cycles
• Two conjectured strengthenings of Turán's theorem
• 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
• Positive and negative square energies of graphs
• Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph
• On the chromatic number of a simplicial complex
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• A characterization and an application of weight-regular partitions of graphs
• Proof of a conjectured lower bound on the chromatic number of a graph
• The estimation of the bound of the sum of squares of positive (negative) eigenvalues of a graph
• Symmetry and asymmetry between positive and negative square energies of graphs
• A lower bound for the chromatic number of a graph
• New eigenvalue bound for the fractional chromatic number
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Spectral lower bounds for the quantum chromatic number of a graph
• Distance Laplacian eigenvalues and chromatic number in graphs
• Spectrum of signless 1-Laplacian on simplicial complexes
• Eigenvalues and chromatic number of a signed graph
• Upper bounds for the achromatic and coloring numbers of a graph
• An inertial lower bound for the chromatic number of a graph
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles

This page was built for publication: New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix

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