Hoffman colorability of graphs with smallest eigenvalue at least -2
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908865530953728 |
|---|---|
| author | De Bruyn, Bart van Veluw, Thijs |
| author_facet | De Bruyn, Bart van Veluw, Thijs |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_03859 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hoffman colorability of graphs with smallest eigenvalue at least -2 De Bruyn, Bart van Veluw, Thijs Combinatorics 05C50, 05C15, 17B22, 05C62 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. |
| title | Hoffman colorability of graphs with smallest eigenvalue at least -2 |
| topic | Combinatorics 05C50, 05C15, 17B22, 05C62 |
| url | https://arxiv.org/abs/2603.03859 |