Hoffman's bound for hypergraphs

Abstract

One of the best-known results in spectral graph theory is the inequality of Hoffman \[ χ\left( G\right) \geq1-\frac{λ\left( G\right) }{λ_{\min }\left( G\right) }, \] where $\chi \left(G\right)$ is the chromatic number of a graph $G$ and $\lambda \left(G\right),$ ${\lambda }_{\min }\left(G\right)$ 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$.

9 pages

References in corpus (1)

• Necessary Spectral Conditions for Coloring Hypergraphs