Tales of Hoffman

2004/07/07 by Yonatan Bilu, Bilu, Yonatan · 3 citations
Mathematics · #05c15 #05c50 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05c15 #msc:05c50

paper · pdf · doi:10.48550/arxiv.math/0407107

short note - 6 pages

arxiv created 2004/07/29 · arxiv updated 2009/12/01

Abstract

Hofmman's bound on the chromatic number of a graph states that χ≥ 1 - \frac λ₁ λ_n. Here we show that the same bound, or slight modifications of it, hold for several graph parameters related to the chromatic number: the vector coloring number, the ψ-covering number and the λ-clustering number.

Cited by

• Tales of Hoffman: from a distance
• Spectral characterizations of local structures of graphs and hypergraphs
• Coloring outside the lines: Spectral bounds for generalized hypergraph colorings

Related

• More Tales of Hoffman: bounds for the vector chromatic number of a graph
• Tales of Hoffman: from a distance
• Hoffman's bound for hypergraphs
• Proof of a conjectured spectral upper bound on the chromatic number of a graph
• Hadwiger number always upper bounds the chromatic number -- 1852-1943 -- A far-reaching generalisation of Guthrie's postulate