Hoffman colorability of graphs with smallest eigenvalue at least − 2 -2
Bart De Bruyn, Thijs van Veluw · 2026
Read Hoffman colorability of graphs with smallest eigenvalue at least − 2 -2 by Bart De Bruyn, Thijs van Veluw (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03859.txt.
Introduction
Bart De Bruyn and Thijs van Veluw classify Hoffman colorability for connected graphs whose smallest eigenvalue is at least minus two. A graph is Hoffman colorable when the spectral Hoffman bound on its chromatic number is tight. Building on the Cameron-Goethals-Seidel-Shult classification theorem, the authors extend an earlier characterization that covered only line graphs to this whole class of graphs.
They characterize Hoffman colorability for generalized line graphs. They also completely classify the exceptional graphs that are Hoffman colorable, finding several hundred of them arranged in a natural partial order, with a small set of maximal ones. As a byproduct they also determine all graphs maximal with respect to being representable in one of the classical root systems. The results complete a chapter of spectral graph theory linking eigenvalues, colorings, and root system geometry.
Catalog record
| CREATOR | Bart De Bruyn, Thijs van Veluw |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 114770 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03859
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hoffman colorability of graphs with smallest eigenvalue at least − 2 -2 Bart De Bruyn, Thijs van Veluw 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 -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 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 E_{7} root system. 1 Introduction For a simple graph G , write \lambda_{\max}(G) and \lambda_{\min}(G) for respectively the largest and smallest eigenvalue of the adjacency matrix of G . The Hoffman bound is a well-known spectral lower bound for the chromatic number of a non-empty graph G : \chi(G)\geq h(G) , where h(G)\coloneqq 1-\frac{\lambda_{\max}(G)}{\lambda_{\min}(G)}. (1) A graph is called Hoffman colorable if the Hoffman bound is tight, and every optimal coloring is then called a Hoffman coloring . From the spectrum of regular complete multipartite graphs K_{m,m,\dots,m} , it can be easily read off that they are Hoffman colorable. Also non-empty bipartite graphs (graphs with chromatic number 2) are Hoffman colorable, since their spectra are symmetric around 0. In both cases, the multipartition is a Hoffman coloring. Bipartite and regular complete multipartite graphs are not the only examples; a Hoffman colorable graph that is neither bipartite nor regular complete multipartite is called non-trivially Hoffman colorable , see for example the graph from Figure 1 . \lambda_{\max}=1+\sqrt{5},\quad\lambda_{\min}=\frac{-1-\sqrt{5}}{2} Figure 1: The smallest connected non-trivially Hoffman colorable graph. Hoffman colorings have been studied in [ 3 , 12 ] for (strongly) regular graphs, and in [ 1 , 2 ] for general graphs. Tightness of a related spectral lower bound for the chromatic number in terms of the eigenvalues of the normalized Laplacian matrix has also been studied [ 4 , 8 ] . In [ 5 , 10 ] , the Hoffman bound is used to classify strongly regular and distance-regular graphs with a given small chromatic number. Studying Hoffman colorability of graphs is interesting because the Hoffman bound is not only a lower bound for the chromatic number, but also for numerous variations of the chromatic number. This includes the vector chromatic number \chi_{v} [ 13 ] , which is related to the Lovász \vartheta -number [ 14 ] (see [ 13 , Theorem 8.2] ), and the quantum chromatic number \chi_{q} ; we have h(G)\leq\chi_{v}(G)\leq\chi_{q}(G)\leq\chi(G) by [ 15 , Corollary 4.1] and [ 14 , Theorem 6] . For a Hoffman colorable graph, we get the values for these variations of the chromatic number for free by sandwiching. In particular, for Hoffman colorable graphs, the quantum chromatic number is computable, while for graphs in general it is not known to be computable [ 15 ] . Of particular interest to this paper are the results of [ 2 ] , which we briefly discuss. The Decomposition Theorem [ 2 , Theorem 3.3] , among other things, entails that the induced subgraph of a connected Hoffman colorable graph on a choice of at least two color classes is again Hoffman colorable. We will refer to such induced subgraphs as chromatic components , so that Hoffman colorability is closed with respect to chromatic components. Using the Decomposition Theorem, one can characterize Hoffman colorability in line graphs [ 2 , Theorem 3.12] ; the line graph L(G) of a non-empty graph G is defined as the graph having the edges of G as vertices, such that two G -edges are adjacent in L(G) whenever they share a vertex. Line graphs have the spectral property that the smallest eigenvalue is bounded below by -2 . The well-known Cameron-Goethals-Seidel-Shult Theorem spectrally generalizes line graphs by classifying all connected graphs having all eigenvalues at least -2 . In short, there is an infinite family, the generalized line graphs , and finitely many exceptional graphs , which can be represented in the E_{8} root system. Induced subgraphs of generalized line graphs are also generalized line graphs. Therefore, if a connected graph G with smallest eigenvalue at least -2 contains an exceptional graph H as an induced subgraph, then G is exceptional as well. This defines a partial order on the set of exceptional graphs, and there are 473 exceptional graphs that are maximal with respect to this partial order [ 9 , Section 6.1] . A very natural follow-up question of the characterization of Hoffman colorable line graphs from [ 2 ] is therefore whether it is possible to extend it to generalized line graphs, or even to exceptional graphs. As it turns out, this is possible, and this is exactly the main subject of this article. In particular, we show that Hoffman colorability of generalized line graphs is equivalent to an explicit condition in terms of the graph structure which we call chromatically balanced . Moreover, we determine that there are exactly 245 Hoffman colorable exceptional graphs and among these, we determine those that are maximal with respect to chromatic components; there are exactly 29 of them. The complete statement of the classification can be found in ?THM? . As an important ingredient of our proof of ?THM? , we find that, among the graphs that can be represented in the E_{7} root system, there are exactly 39 that are maximal with respect to induced subgraphs. Using ?THM? , we completely classify all connected non-trivially Hoffman colorable graphs G with fewer than 3\chi(G) vertices (?THM? ). This article is organized as follows. In Section 2 we present our main contributions. In Section 3 we set out the preliminaries that are necessary for our proofs. In Sections 4 and 5 we prove ?THM? , in the cases of generalized line graphs and exceptional graphs respectively. In Section 6 we prove ?THM? . Lastly, in Section 7 we give (a reference to) an E_{8} -representation for each of the 245 Hoffman colorable exceptional graphs from ?THM? . 2 New classifications of Hoffman colorable graphs In this section we state our main theorem (?THM? ), as well as an application to graphs with fewer than 3\chi(G) vertices (?THM? ). Before stating those results, we need to define some additional notions. Let G and H be two graphs, and let m\geq 2 be an integer. Then we call H an m -chromatic component of G if there exists an optimal coloring of G (say V(G)=\bigsqcup_{i=1}^{\chi(G)}V_{i} where each V_{i} is a coclique) such that H is isomorphic to the induced subgraph of G on the set of vertices \bigsqcup_{i=1}^{m}V_{i} . Instead of 2-chromatic we say dichromatic . For m a non-negative integer, the cocktail party graph CP(m) is the complete multipartite graph with m classes of size 2. If G is a graph on vertices v_{1},\dots,v_{n} , and a_{1},\dots,a_{n}