Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

Hoffman colorability of (strongly) regular graphs

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A product inequality involving the Hoffman bound characterizes strongly regular graphs among regular graphs.

desk verdict Solid paper in algebraic graph theory: the equality characterization in Theorem 5.4 is real but rests on an imported theorem from the authors' own earlier paper [5]. read the letter →

arxiv 2508.18793 v1 pith:QVSOKJKE submitted 2025-08-26 math.CO

Aida Abiad , Bart De Bruyn , Thijs van Veluw This is my paper · ORCID
classification math.CO MSC 05C5005C1505E30
keywords Hoffmanboundcoloringstronglyregulargraphschromaticnumberspectralgraphtheoryuniquevectorcolorabilitypseudo-geometricNeumaier
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper treats the Hoffman bound, the classic eigenvalue lower bound on the chromatic number of a graph, as a number h(G) rather than just a bound, and asks what happens when a graph's chromatic number actually attains it. The central result is a product inequality for regular graphs: h(G)h(complement G) ≤ n, where n is the number of vertices, and equality holds exactly for the strongly regular graphs. In the strongly regular case the paper also proves that attaining the bound forces the graph (and its complement) to be pseudo-geometric, and that only finitely many primitive strongly regular graphs have bounded Hoffman number, listing all those with h ≤ 3. A separate thread shows that non-trivial Hoffman colorability of a connected 2-walk-regular graph prevents unique vector colorability, which covers several strongly regular graphs not reached by earlier criteria. The upshot is that Hoffman colorability is a sharp spectral probe of regularity: many forms of regularity are exactly the conditions that make the bound tight.

What carries the argument

The Hoffman number h(G)=1−λmax/λmin; geometric parameters (s,t,α) for strongly regular graphs, defined from the eigenvalues by s=−k/τ, t=−τ−1, α=s−θ, in which the Hoffman number is simply s+1; and the average parameters (a_av,c_av,τ_av,θ_av,s_av) for arbitrary regular graphs, for which the identity (s_av+1)(s̄_av+1)=n holds. The geometric parameters translate eigenvalue data into projective-geometry data, making pseudo-geometricity and h visible; the average parameters let the strongly-regular identity survive in averaged form and carry the equality characterization.

What would settle it

Enumerate all connected regular graphs up to, say, ten vertices and compute h(G)h(complement G); the theorem predicts equality only for the strongly regular graphs among them. Finding any non-strongly-regular regular graph with product exactly n — or, alternatively, any strongly regular graph whose product misses n — would refute Theorem 5.4. A quicker targeted check: the cube Q3 should give h·h̄ = 2·3 = 6 < 8, while the Petersen graph should give h·h̄ = 10 = n.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that the Hoffman number h(G)=1−λmax(G)/λmin(G) interacts multiplicatively with complementation. For every regular graph, h(G)h(complement G) ≤ n; the product reaches n precisely when G is strongly regular. That turns strong regularity into the saturation case of a spectral inequality and gives a new characterization of strong regularity among regular graphs. The proof routes through average analogues of the strongly regular parameters — averaging the common-neighbor counts and taking the roots of the corresponding quadratic — to obtain the identity (s_av+1)(s̄_av+1)=n and an imported inequality that is strict unless G is strongly regular. Al

Load-bearing premise

The argument depends on an imported result, not proved here, saying that the smallest eigenvalue of a regular graph is at most an averaged version of the smallest strongly-regular eigenvalue, with equality exactly for strongly regular graphs; if that result or its equality case is wrong, the new characterization of strong regularity fails.

Editorial extensions

If this is right

  • Strong regularity is now visible spectrally as equality in h(G)h(complement G) ≤ n; any regular graph with a strictly smaller product is provably not strongly regular.
  • Only finitely many primitive strongly regular graphs have Hoffman number at most any fixed m; for m=3 the complete list is the pentagon, L(K3,3), the Petersen graph, L(K6), the complement of the Clebsch graph, and the complement of the Schläfli graph.
  • A Hoffman coloring of a primitive strongly regular graph implies both the graph and its complement are pseudo-geometric, so optimal colorings correspond to spreads and partial-geometry structure.
  • Non-trivial Hoffman colorability of a connected 2-walk-regular graph rules out unique vector colorability, so graphs like the Shrikhande and Schläfli graphs are non-uniquely vector colorable even though earlier core-based criteria did not cover them.
  • Co-edge-regular but not strongly regular graphs, and strictly Neumaier graphs, cannot be Hoffman colorable; Hoffman colorable regular graphs also satisfy the Neumaier clique bound and a triangle lower bound with equality only in the strongly regular case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The quantity n−h(G)h(complement G) could serve as a spectral measure of how far a regular graph is from strong regularity; testing whether it correlates with other non-regularity measures such as diameter or number of distinct eigenvalues would be a natural next step.
  • Because the paper notes its product inequality is equivalent to a known inequality for parameterized graph pairs, the product form may offer a bridge between Hoffman colorings and that framework; exploring extremal regular graphs where the gap is small is a testable extension.
  • The average-parameter route suggests the same product inequality may admit analogues for other graph matrices, such as the Laplacian or normalized Laplacian, where equality would then characterize a different regularity class.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies the Hoffman number h(G)=1−λmax/λmin and Hoffman colorings for regular, co-edge-regular, and strongly regular graphs. It claims that Hoffman colorable primitive strongly regular graphs and their complements are pseudo-geometric (Theorem 3.3), that only finitely many primitive strongly regular graphs have bounded Hoffman number (Theorem 3.7), that non-trivially Hoffman colorable connected 2-walk-regular graphs are not uniquely vector colorable (Theorem 4.1), and that for every regular graph h(G)h(complement G) ≤ n with equality exactly for strongly regular graphs (Theorem 5.4). It also gives applications to Neumaier graphs, co-edge-regular graphs, and triangle counts. The main Section 5 derivation is coherent, but several statements and proofs in Section 3 contain internal inconsistencies that need correction.

Significance. If the results are correct, the paper provides a new spectral characterization of strong regularity as the saturation of a product Hoffman bound, strengthens Haemers' finiteness theorem by replacing chromatic number with the smaller Hoffman number, and broadens known non-unique vector colorability results. The authors are generally careful to state what is imported from [5] and what is new. However, the Section 3 finiteness proof currently relies on a false identity, and the enumeration in Corollary 3.8 is inconsistent with its own proof and with standard graph names. These issues are fixable, but they affect two of the stated main results.

major comments (4)
  1. [Section 3, Theorem 3.7] The proof asserts, after bounding θ, that 'τ = −1 − θ'. This does not follow from (12). In the geometric parameters (12), θ = s − α and τ = −t − 1, and t need not equal s − α. For example, the Kneser graph K(6,2) has h=3, θ=1, τ=−3, while −1−θ = −2. The argument bounding |τ| from h≤m therefore needs repair; this is load-bearing for the finiteness theorem.
  2. [Corollary 3.8 and Example 3.5] The list in Corollary 3.8 is inconsistent with its proof and with the notation used elsewhere. The graph listed as 'L(K6)' with geometric parameters (2,2,1) and h=3 is the complement of the triangular graph T(6), i.e. the Kneser graph K(6,2); L(K6)=T(6) itself has h=5 and geometric parameters (4,1,2). Example 3.5 simultaneously says L(K6) has h=5 and is the collinearity graph of a (2,2,1)-partial geometry, which is impossible. Likewise, the entry 'complement of the Clebsch graph' with parameters (5/3,2,2/3) and h=8/3 is actually the Clebsch graph; its complement has parameters (5,1,3) and h=6. The proof also states τ=−2 for all non-conference cases, but K(6,2) and the Clebsch graph have τ=−3. Please correct the names and the classification argument.
  3. [Section 5, Theorem 5.4 and Remark 5.2] The equality characterization of strong regularity is the central claim of the paper, but it rests entirely on the imported inequality (16), h(G) ≤ s_av + 1 with equality iff G is strongly regular, taken from [5, Theorem 2.14(a)] and [5, Theorem 2.30] via Remark 5.2. Since [5] shares two authors with the present paper and the equality condition is essential, the authors should state the exact imported theorems and either reproduce a proof of (16) or verify its equality condition explicitly. As written, the central theorem is only as secure as a result quoted from overlapping-author work.
  4. [Section 5, Corollary 5.8] In the proof of Corollary 5.8, part (iii) says it 'follows similarly from (17)', but a Hoffman clique in G has size n/h(complement G), whereas (17) compares s_av + 1 with n/h(G). The implication is not transparent as written. Please spell out the argument (e.g. using a Hoffman clique to force h(G)h(complement G)=n via the Hoffman coloring) or correct the cited equation.
minor comments (4)
  1. [Section 3] Please standardize the notation for triangular graphs and their complements; write T(6)=L(K_6) and its complement as \(\overline{L(K_6)}\), or use the Kneser graph name, to avoid the ambiguity in Example 3.5 and Corollary 3.8.
  2. [After Lemma 5.3] The claim about irregular graphs using average degree is unproved and unused. Consider removing it or providing a proof.
  3. [Theorem 3.7 proof] The phrase 'Applying Theorem 3.6 to every integer at most m' will need adjustment once the correct bound on τ is established; based on the intended argument it should likely be integers at most m−1 or m, depending on the repaired inequality.
  4. [Section 5, Theorem 5.4] The statement of Theorem 5.4 does not repeat the standing assumption that G is neither empty nor complete. Please make this explicit in the theorem statement.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central claim is derived from in-paper algebra plus an external published theorem, not from its own conclusion.

full rationale

Walking the derivation chain, no step reduces to its own input by construction. The main inequality h(G)h(G) ≤ n is proved by combining Lemma 5.3, an algebraic identity proved in this paper, with inequality (16). Inequality (16) is imported from [5, Theorem 2.14(a)] via Remark 5.2; although [5] shares two authors with the present paper, the cited theorem is a published, parameter-free external result whose assumptions (regular graph and average parameters) do not include the conclusion h(G)h(G) ≤ n or the strong-regularity equality characterization. Thus it is real evidence, not circularity. The equality characterization of Theorem 5.4 is not definitionally equal to [5]'s statement: it requires Lemma 5.3 and applying (16) to both G and its complement. Section 3's geometric parameters are definitions, not fitted values; Theorem 3.3 and Theorem 3.7 follow from algebra and cited classifications. Theorem 4.1 uses external vector-coloring results. Corollary 5.8(iv) is not circular: Proposition 2.1 converts the Hoffman coloring of the complement into a Hoffman clique, enabling part (iii). The only noteworthy risk is that Theorem 5.4's equality direction depends on an unproved-in-this-paper theorem from overlapping-author work [5]; that is an omitted proof / external dependency, not a self-justifying reduction, and per the review rules it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new entities and fits no free parameters. Its claims depend instead on standard spectral graph theory, on classification theorems for strongly regular graphs, and on one load-bearing inequality from the authors' earlier paper [5] which is not re-proved here.

assumptions (6)
  • domain assumption In a regular graph, λmin(G) ≤ τ_av, with equality iff G is strongly regular (imported as [5, Theorem 2.14(a)]).
    Used to derive inequality (16) and the equality characterization in Theorem 5.4; not proved in this paper and from a paper with overlapping authors.
  • domain assumption There are only finitely many primitive strongly regular graphs with smallest eigenvalue τ = -m apart from geometric graphs with α ∈ {t, t+1} ([8, Theorem 9.1.9]).
    Core external input for Theorem 3.7.
  • domain assumption The strongly regular graphs with least eigenvalue -2 are classified ([8, Theorem 9.2.1]).
    Used in Corollary 3.8 to list the graphs with Hoffman number at most 3.
  • domain assumption Optimal vector colorings of 2-walk-regular graphs are locally injective ([14, Lemma 3.11]), and each 1-walk-regular graph has an optimal vector coloring ([13, Corollary 4.11]).
    Used in the proof of Theorem 4.1 to produce two optimal vector colorings with different local injectivity.
  • standard math Brooks' theorem: connected graph with max degree Δ and not complete or odd cycle has χ ≤ Δ.
    Used in Theorem 4.1 to show that a non-trivial Hoffman coloring is not locally injective.
  • domain assumption Hoffman colorings of strongly regular graphs correspond to spreads in the complement ([21]).
    Used in Theorem 3.3 to conclude that the complement of a Hoffman colorable strongly regular graph is also pseudo-geometric.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hoffman colorability of (strongly) regular graphs." pith.science (2026). https://pith.science/paper/QVSOKJKE

@misc{pith2026250818793,
  author       = {Pith},
  title        = {Pith review of: Hoffman colorability of (strongly) regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QVSOKJKE}},
  note         = {Machine review of arXiv:2508.18793}
}
read the original 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, \v{S}\'amal 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A graph energy conjecture through the lenses of semidefinite programming

    math.CO 2025-09 reject novelty 6.0 of 10

    New SDP-based bounds relate graph energy to the fractional clique cover number, Hoffman's ratio number, and Schrijver's theta number, supporting a 40-year-old conjecture without proving it.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [5]

    Abiad, B

    A. Abiad, B. De Bruyn, J. D’haeseleer, and J. H. Koolen. Neumaier graphs with few eigenvalues. Des. Codes Cryptogr. , 90(9):2003–2019, 2022

    work page 2003

  2. [14]

    Godsil, D

    C. Godsil, D. E. Roberson, B. Rooney, R. ˇS´ amal, and A. Varvitsiotis. Graph homomorphisms via vector colorings. European J. Combin., 79:244–261, 2019

    work page 2019

  3. [1]

    A. Abiad. A characterization and an application of weight-regular partitions of graphs. Linear Algebra Appl., 569:162–174, 2019

    work page 2019

  4. [2]

    Abiad, W

    A. Abiad, W. Bosma, and T. van Veluw. Hoffman colorings of graphs. Linear Algebra Appl. , 710:129–150, 2025

    work page 2025

  5. [3]

    Abiad, W

    A. Abiad, W. Castryck, M. De Boeck, J. H. Koolen, and S. Zeijlemaker. An infinite class of Neumaier graphs and non-existence results. J. Comb. Theory, Ser. A , 193: Paper No. 105684, 2023

    work page 2023

  6. [4]

    Abiad, M

    A. Abiad, M. De Boeck, and S. Zeijlemaker. On the existence of small strictly Neumaier graphs. Graphs Comb., 40(3): Paper No. 51, 2024

    work page 2024

  7. [6]

    Beers and R

    L. Beers and R. Mulas. At the end of the spectrum: chromatic bounds for the largest eigenvalue of the normalized Laplacian. Journal of Physics: Complexity , 6(2), 2025

    work page 2025

  8. [7]

    Blokhuis, A

    A. Blokhuis, A. E. Brouwer, and W. H. Haemers. On 3-chromatic distance-regular graphs. Des. Codes Cryptogr., 44(1–3):293–305, 2007

    work page 2007

Show all 31 references
  1. [8]

    A. E. Brouwer and W. H. Haemers. Spectra of graphs. Universitext. Springer, New York, 2012

    2012

  2. [9]

    P. J. Cameron. Strongly regular graphs. In: Topics in algebraic graph theory (L. W. Beineke and R. J. Wilson, editors), Encycl. Math. Appl. , 102. Cambridge University Press, Cambridge, 2004

    2004

  3. [10]

    Coutinho, R

    G. Coutinho, R. Grandsire, and C. Passos. Colouring the normalized Laplacian. Electron. Notes Theor. Comput. Sci. , 346:345–354, 2019

    2019

  4. [11]

    Delsarte

    P. Delsarte. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10, 1973

    1973

  5. [12]

    R. J. Evans, S. Goryainov, and D. Panasenko. The smallest Neumaier graph and its generalisations. Electron. J.Comb., 26(2): Paper No. P2.29, 2019

    2019

  6. [13]

    Godsil, D

    C. Godsil, D. E. Roberson, B. Rooney, R. ˇS´ amal, and A. Varvitsiotis. Universal completability, least eigenvalue framework, and vector colorings. Discrete Comput. Geom. , 58(2):265–292, 2017

    2017

  7. [15]

    Godsil, D

    C. Godsil, D. E. Roberson, R. ˇS´ amal, and S. Severini. Sabidussi versus Hedetniemi for three variations of the chromatic number. Combinatorica, 36(4):395–415, 2016

    2016

  8. [16]

    Godsil and G

    C. Godsil and G. Royle. Algebraic graph theory , Grad. Texts Math. , 207. Springer-Verlag, New York, 2001. 13

    2001

  9. [17]

    G. R. W. Greaves and J. H. Koolen. Edge-regular graphs with regular cliques. Eur. J. Comb. , 71:194–201, 2018

    2018

  10. [18]

    G. R. W. Greaves and J. H. Koolen. Another construction of edge-regular graphs with regular cliques. Discrete Math., 342(10):2818–2820, 2019

    2019

  11. [19]

    W. H. Haemers. Eigenvalue techniques in design and graph theory. Dissertation, Technische Hogeschool Eindhoven, 1979

    1979

  12. [20]

    W. H. Haemers. Hoffman’s ratio bound. Linear Algebra Appl., 617:215–219, 2021

    2021

  13. [21]

    W. H. Haemers and V. D. Tonchev. Spreads in strongly regular graphs. Des. Codes Cryptogr. , 8(1–2):145–157, 1996

    1996

  14. [22]

    A. J. Hoffman. On eigenvalues and colorings of graphs. Graph Theory Appl., Proc. Advanced Sem. Wisconsin, Madison 1969, 79–91, 1970

    1969

  15. [23]

    Karger, R

    D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246–265, 1998

    1998

  16. [24]

    Lov´ asz

    L. Lov´ asz. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory , 25(1):1–7, 1979

    1979

  17. [25]

    R. J. McEliece, E. R. Rodemich, and H. C. Rumsey Jr.. The Lov´ asz bound and some generaliza- tions. J. Combin. Inform. System Sci. , 3(3):134–152, 1978

    1978

  18. [26]

    Finite geometries and designs

    A. Neumaier. Regular cliques in graphs and special 1 1 2 -designs. In “Finite geometries and designs”, Proc. 2nd Isle of Thorns Conf. 1980, London Math. Soc. Lecture Note Ser. , 49:244–259, 1981

    1980

  19. [27]

    Pak and D

    I. Pak and D. Vilenchik. Constructing uniquely realizable graphs. Discrete Comput. Geom. , 50(4):1051–1071, 2013

    2013

  20. [28]

    D. E. Roberson. Homomorphisms of strongly regular graphs. Algebr. Comb., 2(4):481–497, 2019

    2019

  21. [29]

    D. E. Roberson. On ( α, β)-Graphs. Preprint (private communication), 2025

    2025

  22. [30]

    Schrijver

    A. Schrijver. A comparison of the Delsarte and Lov´ asz bounds. IEEE Trans. Inform. Theory , 25:425–429, 1979

    1979

  23. [31]

    Yang and J

    Q. Yang and J. H. Koolen. Edge-regular graphs with fixed smallest eigenvalue with an application to Neumaier graphs. Discrete Math., 348(7): Paper No. 114489, 2025. 14

    2025

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.