Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
From MaRDI portal
Publication:2496209
DOI10.1016/j.jctb.2005.10.002zbMath1094.05036arXivmath/0407107OpenAlexW2002478783MaRDI QIDQ2496209
Publication date: 12 July 2006
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0407107
chromatic numberpositive semidefinite matricesHoffman's bound\(\lambda\)-clustering number\(\psi\)-covering numbervector coloring number
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)
Related Items
New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix ⋮ New eigenvalue bound for the fractional chromatic number ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ An inertial lower bound for the chromatic number of a graph ⋮ Spectral theory of Laplace operators on oriented hypergraphs ⋮ Fractional decompositions and the smallest-eigenvalue separation ⋮ 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 ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming ⋮ More tales of Hoffman: bounds for the vector chromatic number of a graph
Cites Work
