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

zbMath1295.05112arXiv1209.3190MaRDI QIDQ396873

Clive Elphick, Paweł Wocjan

Publication date: 14 August 2014

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

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

zbMATH Keywords

chromatic numberspectral graph theoryHoffman bound

Mathematics Subject Classification ID

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

Related Items

Conjectured bounds for the sum of squares of positive eigenvalues of a graph, Spectrum of signless 1-Laplacian on simplicial complexes, Unified spectral bounds on the chromatic number, A characterization and an application of weight-regular partitions of graphs, Positive and negative square energies of graphs, Two conjectured strengthenings of Turán's theorem, New eigenvalue bound for the fractional chromatic number, Unnamed Item, Distance Laplacian eigenvalues and chromatic number in graphs, Upper bounds for the achromatic and coloring numbers of a graph, An inertial lower bound for the chromatic number of a graph, Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph, Eigenvalues and chromatic number of a signed graph, On the chromatic number of a simplicial complex, Proof of a conjectured lower bound on the chromatic number of a graph, Optimization of eigenvalue bounds for the independence and chromatic number of graph powers, Spectral lower bounds for the orthogonal and projective ranks of a graph, Spectral lower bounds for the quantum chromatic number of a graph, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, More tales of Hoffman: bounds for the vector chromatic number of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectra of graphs
• Lower bounds for the clique and the chromatic numbers of a graph
• Walks and the spectral radius of graphs
• Orthogonal vector coloring
• Chromatic number and spectral radius
• On the quantum chromatic number of a graph
• Spectral bounds for the clique and independence numbers of graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• Cliques and the spectral radius
• Some Inequalities for the Largest Eigenvalue of a Graph
• Coloring an Orthogonality Graph
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• A lower bound on the chromatic number of a graph
• The chromatic number of random graphs