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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Hoffman colorability of (strongly) regular graphs

Bart De Bruyn, Aida Abiad, Thijs van Veluw
Discrete Mathematics
Graph Labeling and Dimension Problems
article

Hoffman colorability of (strongly) regular graphs

Bart De Bruyn, Aida Abiad, Thijs van Veluw
article en

Abstract

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.

Discrete MathematicsVol. 349(3)
HOGENT University of Applied Sciences and Arts (BE), Vrije Universiteit Brussel (BE), Ghent University (BE), Eindhoven University of Technology (NL)
Nederlandse Organisatie voor Wetenschappelijk Onderzoek, Universiteit Gent, Bijzonder Onderzoeksfonds UGent
Openalex Percentile: Top 67%
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Hoffman colorability of (strongly) regular graphs — Bart De Bruyn, Aida Abiad, et al. · Discrete Mathematics (2025) | TGRS Research Map | TGRS