Hoffman Ratio Bound

The Hoffman ratio bound, also called the Hoffman bound, is an upper bound on the independence number of a regular graph in terms of its least graph eigenvalue. If is a regular graph of vertex degree on vertices and has least graph eigenvalue , then

(1)

If an independent vertex set meets the bound, then every vertex outside the set has exactly neighbors in it. Applying the bound to the graph complement gives the corresponding upper bound on the clique number. For a strongly regular graph, the latter bound agrees with the Delsarte bound.

Every color class in a vertex coloring is an independent vertex set, so the chromatic number satisfies

(2)

where is the ceiling function. For a strongly regular graph, the least graph eigenvalue is determined by its common-neighbor parameters.

More generally, for a simple graph with at least one graph edge, the spectral lower bound on the chromatic number is

(3)

where and are the largest and least adjacency eigenvalues (Brouwer and Haemers 2012). This form does not require the graph to be regular.

The independence-number form of the Hoffman ratio bound is due to A. J. Hoffman, but was not published by him. Lovász (1979, Thm. 9) published a bound using the Lovász number that implies the Hoffman ratio bound, and Haemers (2021) gives a historical account. The Hoffman ratio bound is the case of the Haemers regular upper bound.