New SDP-based bounds relate graph energy to the fractional clique cover number, Hoffman's ratio number, and Schrijver's theta number, supporting a 40-year-old conjecture without proving it.
Hoffman colorability of (strongly) regular graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Hoffman's bound is a well-known eigenvalue bound on the chromatic number of a graph. By interpreting this bound as a parameter, we show multiple applications of colorings attaining the bound (Hoffman colorings) for several notions of graph regularity: regular, (co-)edge-regular, and strongly regular. For strongly regular graphs, we prove that Hoffman colorability implies pseudo-geometricity, and we strengthen Haemers' finiteness result on strongly regular graphs with a bounded chromatic number by considering the Hoffman bound instead of the chromatic number. Furthermore, by using Hoffman colorings we show that a sufficient condition for non-unique vector colorability shown by Godsil, Roberson, Rooney, \v{S}\'amal and Varvitsiotis [European J. Combin. 79, 2019] can be relaxed in the setting of strongly regular graphs. Lastly, using Hoffman colorings we derive several new characterizations of the mentioned graph regularity notions.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
REJECT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
A graph energy conjecture through the lenses of semidefinite programming
New SDP-based bounds relate graph energy to the fractional clique cover number, Hoffman's ratio number, and Schrijver's theta number, supporting a 40-year-old conjecture without proving it.