Hoffman colorability of graphs with smallest eigenvalue at least -2

This paper extends the characterization of Hoffman colorability to all connected graphs with smallest eigenvalue at least $-2$ by classifying generalized line graphs and exceptional graphs, while identifying 29 maximal exceptional graphs and 39 maximal $E_7$-representable graphs.

The Gist

Imagine you have a giant, complex puzzle made of dots (vertices) and lines (edges). Your goal is to color every dot so that no two dots connected by a line share the same color. You want to use as few colors as possible. This is the classic "Graph Coloring" problem.

Now, imagine there is a magical crystal ball (mathematical formulas involving eigenvalues) that can predict the minimum number of colors you must use. This prediction is called the Hoffman Bound.

Usually, the crystal ball gives you a "best guess" that is lower than the actual number of colors you need. But sometimes, the crystal ball is perfect. When the predicted number matches the actual number needed, we call the graph "Hoffman Colorable." It's like the puzzle has a hidden, perfect symmetry that makes the solution obvious to the crystal ball.

This paper is a massive detective story where the authors, Bart and Thijs, go on a quest to find every single puzzle that is "Hoffman Colorable" within a specific, tricky category of puzzles.

The Setting: The "No-Go" Zone

The authors are looking at a specific family of puzzles where the "lines" between dots have a special property: their "smallest eigenvalue" (a fancy number describing the graph's shape) is at least -2.

Think of this as a rule: "We are only looking at puzzles that aren't too twisted."
Mathematicians already knew that these puzzles fall into two main camps:

1. The Generalized Line Graphs: These are like puzzles built from other puzzles (specifically, puzzles made of edges). They are the "regular" citizens of this world.
2. The Exceptional Graphs: These are the "weirdos" or "aliens." They don't fit the standard pattern. There are only a finite number of them, and they are rare and special.

The Mission: The Great Classification

The authors wanted to answer a simple question: "Which of these puzzles are perfectly Hoffman Colorable?"

They already knew the answer for the "regular" puzzles (line graphs). But they wanted to extend this to the "weird" ones (exceptional graphs) and the "generalized" ones.

Here is what they found, translated into everyday terms:

1. The "Balanced" Regular Puzzles

For the generalized line graphs, they found a simple rule. A puzzle is perfectly colorable if it is "Chromatically Balanced."

• The Analogy: Imagine a seesaw. For the puzzle to work perfectly, the weight on every side must be perfectly distributed. If you have a "cocktail party" (a group of people where everyone knows everyone else in pairs) attached to a vertex, the number of people in that party must perfectly match the number of connections that vertex has to the rest of the puzzle. If the math balances, the puzzle is solvable in the optimal way.

2. The "Alien" Puzzles (Exceptional Graphs)

This is the big discovery. The authors went through the entire zoo of "weird" puzzles (there are 473 of them that are "maximal," meaning you can't add any more lines without breaking the rules) and asked: "Which of these are perfectly colorable?"

• The Result: They found 245 perfectly colorable "aliens."
• The Hierarchy: They realized these 245 puzzles aren't random. They are like a family tree. Some are small pieces of others.
• The "Kings": At the top of this family tree, there are 29 "Maximal" graphs. Think of these as the "Kings" or "Bosses." Every other Hoffman colorable exceptional graph is just a smaller piece (a "chromatic component") of one of these 29 bosses.
  • Analogy: Imagine you have 29 giant, intricate Lego castles. If you take a piece off one, you might get a smaller castle that is still perfectly colorable. The authors mapped out every single piece that can be taken off these 29 castles to make a valid, smaller, colorable castle.

3. The "Small" Puzzles

They also looked at puzzles that are very small compared to how many colors they need.

• The Finding: There are exactly 10 such puzzles that are non-trivial (meaning they aren't just simple bipartite graphs or complete graphs).
• The Analogy: It's like finding that there are only 10 specific types of tiny, complex knots that can be untied perfectly. They identified exactly what these 10 knots look like.

The Tools of the Trade

How did they do this?

• The Crystal Ball (Eigenvalues): They used advanced spectral math to filter out the impossible candidates.
• The Decomposition Theorem: This is like a rule that says, "If the whole puzzle is perfectly colorable, then any piece of it made of two colors must also be perfectly colorable." This allowed them to break big problems into smaller, manageable chunks.
• The Root System (E8): This is the "DNA" of these puzzles. The "Exceptional" graphs can be built using vectors from a complex 8-dimensional shape called the E8 root system. The authors used this 8D geometry to construct and verify their 245 graphs.
• Computer Brains: They used software (SageMath) to check thousands of combinations, essentially asking the computer to try every possible way to color these graphs and see if it matches the crystal ball's prediction.

The "Byproduct": The E7 Mystery

While hunting for the 245 graphs, they stumbled upon another treasure. They found 39 graphs that are "maximal" in a slightly different 7-dimensional system called E7.

• The Analogy: While looking for the "Kings" of the 8D world, they accidentally mapped out the entire kingdom of the 7D world. They found 39 "Lords" that rule over all other 7D puzzles.

Summary

In plain English, this paper is a comprehensive catalog.

1. It tells you exactly which "weird" puzzles (exceptional graphs) have a perfect, optimal coloring solution.
2. It organizes them into a family tree, showing that they all come from 29 "Boss" graphs.
3. It provides the "blueprints" (mathematical representations) for every single one of these 245 graphs and the 39 related 7D graphs.

It's like the authors walked into a vast, dark library of mathematical puzzles, turned on the lights, and said, "Here are all the puzzles that have a perfect solution. Here is the list of the 29 master puzzles, and here is every single piece you can cut from them that still works."

Technical Summary

Here is a detailed technical summary of the paper "Hoffman colorability of graphs with smallest eigenvalue at least −2" by Bart De Bruyn and Thijs van Veluw.

1. Problem Statement

The paper addresses the problem of characterizing Hoffman colorable graphs within the specific class of connected graphs whose smallest eigenvalue ($\lambda_{\min}$) is at least $-2$.

• Hoffman Colorability: A graph $G$ is Hoffman colorable if its chromatic number $\chi(G)$ equals the Hoffman bound $h(G) = 1 - \frac{\lambda_{\max}(G)}{\lambda_{\min}(G)}$.
• Context: Previous work (Abiad et al., 2025) characterized Hoffman colorability for line graphs. The Cameron-Goethals-Seidel-Shult (CGSS) Classification Theorem states that all connected graphs with $\lambda_{\min} \ge -2$ fall into two categories:
  1. Generalized Line Graphs (GLGs): An infinite family.
  2. Exceptional Graphs: A finite set of graphs representable in the $E_8$ root system.
• Goal: Extend the characterization of Hoffman colorability from standard line graphs to the entire class of graphs with $\lambda_{\min} \ge -2$, including generalized line graphs and exceptional graphs.

2. Methodology

The authors employ a combination of spectral graph theory, algebraic combinatorics, and computational algebra systems (specifically SageMath).

• Spectral Analysis: Utilization of the Hoffman bound, the Decomposition Theorem (relating the spectrum of a graph to its chromatic components), and properties of the Perron-Frobenius eigenvector.
• Structural Characterization:
  • Defining chromatically balanced generalized line graphs.
  • Analyzing dichromatic components (induced subgraphs formed by two color classes) which must be Smith or Dynkin graphs (graphs with $\lambda_{\max} \le 2$).
  • Using Seidel switching to relate exceptional graphs to line graphs of 8-vertex graphs (class $S_8$).
• Root System Representations: Leveraging the $E_8$, $E_7$, and $D_6$ root systems to represent vertices as vectors. Adjacency is determined by the angle between vectors ($60^\circ$for adjacent,$90^\circ$ for non-adjacent).
• Computational Enumeration:
  • Algorithm 1: Computes maximal regular non-trivially Hoffman colorable induced subgraphs by finding cocliques in "Hoffman coclique graphs."
  • Algorithm 2: Computes Hoffman colorable induced subgraphs for irregular graphs by analyzing maximal cocliques in a specific graph $M(G)$ constructed from the input graph.
  • The authors systematically filter the known lists of exceptional graphs (from Cvetković et al.) to identify those satisfying the Hoffman condition.

3. Key Contributions and Results

A. Complete Classification (Theorem 2.1)

The paper provides a complete characterization of all connected, non-trivially Hoffman colorable graphs with $\lambda_{\min} \ge -2$. They are precisely:

1. Chromatically Balanced Generalized Line Graphs: Defined as $L(G; a_1, \dots, a_n)$ where the parameters satisfy a specific balance condition ensuring the chromatic number matches the Hoffman bound.
2. A Sporadic Graph: The graph in Figure 1 (the line graph of the graph in Figure 2), which is the unique non-trivially Hoffman colorable graph with $\lambda_{\min} > -2$.
3. 245 Exceptional Graphs: These are all chromatic components of 29 maximal Hoffman colorable exceptional graphs ($M_1, \dots, M_{29}$).

B. Classification of Exceptional Graphs

The authors classify the 245 Hoffman colorable exceptional graphs based on the sizes of their color classes ($C(G)$). They are divided into eight classes:

• Regular Graphs: 174 graphs (17 with ratio bound 3, 70 with ratio bound 4, and 87 cone graphs).
• Irregular Graphs in $S_8$: 35 graphs (switching-equivalent to line graphs of 8-vertex graphs).
• Remaining Irregular Graphs: 36 graphs (induced subgraphs of maximal exceptional graphs of types (b) and (c), or maximal $E_7$-representable graphs).

Maximal Graphs: The 29 maximal graphs ($M_1$ to $M_{29}$) are identified. Their properties (order, degree sequence, spectrum, and color class sizes) are detailed in Tables 1 and 2.

C. Graphs with Few Vertices (Theorem 2.2)

The paper proves that there are exactly 10 connected non-trivially Hoffman colorable graphs with fewer than $3\chi(G)$ vertices. These are:

• The sporadic graph from Figure 1.
• $M_{10}$ and $M_{21}$.
• Seven chromatic components of $M_{21}$ (of orders 11, 13, 15, 17, and 20).

D. $E_7$-Representable Graphs

As a byproduct, the authors classify all graphs representable in the $E_7$ root system. They identify exactly 39 maximal such graphs (including the Schl"afli graph and 27 cone graphs).

E. Explicit Representations

Section 7 provides explicit $E_8$ and $E_7$ vector representations for all 245 Hoffman colorable exceptional graphs and the 39 maximal $E_7$-representable graphs, utilizing specific vector types ($a_{ij}, b_{ij}, c_{ij}, d_{ijk\ell}$) from the root systems.

4. Significance

• Extension of Theory: This work successfully extends the Hoffman colorability characterization from line graphs to the entire spectral class of graphs with $\lambda_{\min} \ge -2$, resolving a natural follow-up question to previous literature.
• Computational Rigor: The paper bridges theoretical spectral graph theory with extensive computational verification, providing a definitive list of 245 exceptional graphs and their structural properties.
• Quantum and Vector Chromatic Numbers: By identifying Hoffman colorable graphs, the paper implicitly determines the values of the vector chromatic number ($\chi_v$) and quantum chromatic number ($\chi_q$) for these graphs, as they coincide with the standard chromatic number for Hoffman colorable graphs.
• Structural Insight: The classification reveals deep connections between Hoffman colorability, root systems ($E_8, E_7$), and the structure of dichromatic components (Smith/Dynkin graphs). It demonstrates that the "maximal" structures in this domain are finite and explicitly enumerable.

In summary, the paper provides a definitive taxonomy of Hoffman colorability for a major spectral class of graphs, offering both theoretical characterizations and concrete computational data for all relevant exceptional cases.