Hoffman colorability of (strongly) regular graphs
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, Šámal 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.
Authors
- Bart De Bruyn (ORCID: https://orcid.org/0000-0003-4941-7934)
- Aida Abiad (ORCID: https://orcid.org/0000-0003-4003-4291)
- Thijs van Veluw
Institutions
- HOGENT University of Applied Sciences and Arts (BE)
- Vrije Universiteit Brussel (BE)
- Ghent University (BE)
- Eindhoven University of Technology (NL)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2025-10-27
- DOI
- https://doi.org/10.1016/j.disc.2025.114856
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- Universiteit Gent
- Bijzonder Onderzoeksfonds UGent