New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
From MaRDI portal
(Redirected from Publication:396873)
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 . 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3425628 (Why is no real title available?)
- scientific article; zbMATH DE number 3668627 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 3349875 (Why is no real title available?)
- scientific article; zbMATH DE number 3394189 (Why is no real title available?)
- A lower bound for the chromatic number of a graph
- A lower bound on the chromatic number of a graph
- An introduction to the theory of graph spectra
- Approximate graph coloring by semidefinite programming
- Chromatic number and spectral radius
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Cliques and the spectral radius
- Coloring an Orthogonality Graph
- Lower bounds for the clique and the chromatic numbers of a graph
- On the Shannon capacity of a graph
- On the quantum chromatic number of a graph
- Orthogonal vector coloring
- Some Inequalities for the Largest Eigenvalue of a Graph
- Spectra of graphs
- Spectral bounds for the clique and independence numbers of graphs
- Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
- The chromatic number of random graphs
- Walks and the spectral radius of graphs
Cited in
(23)- Unified spectral bounds on the chromatic number
- More tales of Hoffman: bounds for the vector chromatic number of a graph
- A Brualdi-Hoffman-Turán problem on cycles
- Two conjectured strengthenings of Turán's theorem
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph
- Positive and negative square energies of graphs
- 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
- Spectrum of signless 1-Laplacian on simplicial complexes
- Distance Laplacian eigenvalues and chromatic number in graphs
- 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)
