Hoffman colorability of graphs with smallest eigenvalue at least -2

Read full text
Authors: Bart De Bruyn, Thijs van Veluw
Cited by: 0

Abstract

In accordance with the Cameron-Goethals-Seidel-Shult Classification Theorem, we extend the characterization of Hoffman colorability of line graphs from (Abiad, Bosma, Van Veluw, 2025) to all connected graphs with smallest eigenvalue at least $-2$; we give a characterization of Hoffman colorability of generalized line graphs, and we completely classify the Hoffman colorable exceptional graphs. The 245 Hoffman colorable exceptional graphs from this classification admit a natural partial ordering, and we determine the 29 graphs that are maximal in this respect, in a way similar to the classification of maximal ($E_8$-representable) exceptional graphs as described in (Cvetković, Rowlinson, Simić, 2004). Lastly, as a byproduct and also similarly as in (loc. cit.), we determine all 39 graphs that are maximal with respect to being representable in the $E_7$ root system.

Fields of Study & Subjects

Graph theory and applications Finite Group Theory Research Advanced Graph Theory Research

Publication details

Journal / source
arXiv (Cornell University)
Publication date
4 March 2026
Language
EN
Document type
Preprint