Hoffman's bound for hypergraphs

2019/08/05 by Nikiforov, V. · 1 citation
#15A42 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.01433

Abstract

One of the best-known results in spectral graph theory is the inequality of Hoffman χ( G) ≥1-\fracλ( G) λ_min ( G) , where χ( G) is the chromatic number of a graph G and λ( G) , λ_min( G) are the largest and the smallest eigenvalues of its adjacency matrix. In this note Hoffman's inequality is extended to weighted uniform r-graphs for every even r.

Cited by

• Coloring outside the lines: Spectral bounds for generalized hypergraph colorings

Related

• Chromatic number and spectral radius
• More Tales of Hoffman: bounds for the vector chromatic number of a graph
• Unified spectral bounds on the chromatic number
• Proof of a conjectured spectral upper bound on the chromatic number of a graph
• Tales of Hoffman: from a distance