{"id":"97e4ea35-859a-4b5a-8cba-5692069139de","arxiv_id":"2508.18793","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For regular graphs G, h(G)h(complement G) ≤ n, with equality exactly when G is strongly regular; Hoffman colorability forces pseudo-geometricity and finiteness.","lead":"This paper studies graphs whose chromatic number exactly meets a classic eigenvalue lower bound, called Hoffman colorings. It proves new structural restrictions: such graphs are often strongly regular or pseudo-geometric, and only finitely many strongly regular graphs can have a small Hoffman number.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.4's equality characterization rests on inequality (16), imported from overlapping-author paper [5] without proof; if that inequality fails, the central characterization collapses.","rationale":"The stress-test identifies the same load-bearing concern as the reader: Theorem 5.4's equality direction is wholly dependent on inequality (16), which is not proved in the paper but imported from [5] by overlapping authors. I checked the internal logic of the proof: Lemma 5.3 gives (s_av+1)(\\bar{s}_av+1)=n, and the inequality h ≤ s_av+1 for G and its complement yields h h̄ ≤ n. Equality forces equality in both inequalities, so the characterization is valid if and only if (16) holds with the stated equality condition. The paper offers no independent verification, and the cited theorem's exact statement is not reproduced. This is a genuine soft spot, not a manufactured one. I also noticed a likely typo in Corollary 3.8/Example 3.5: L(K6) is listed with geometric parameters (2,2,1), but L(K6) has h=5 and parameters (4,1,2); the graph with (2,2,1) is its complement. This does not affect Theorem 5.4 but suggests cautious proofreading. Overall, the paper is a solid contribution, but the central characterization should be accepted conditionally pending verification of (16).","tokens_in":13004,"tokens_out":11650,"duration_ms":105943,"concrete_test":"Independently verify inequality (16) from first principles: for a k-regular graph, compute a_av, c_av, and τ_av as the smaller root of (15), and prove λ_min(G) ≤ τ_av with equality iff G is strongly regular. Alternatively, perform a computational search over all regular graphs on n ≤ 9 vertices (using Sage or a brute-force adjacency enumeration), compute h(G)h(\\bar G) and compare with n, and confirm that equality occurs exactly for strongly regular graphs. If any regular non-strongly-regular graph attains equality, Theorem 5.4 is disproved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's headline result, Theorem 5.4, states that for a regular graph G, h(G)h(\\bar G) ≤ n with equality iff G is strongly regular. The proof hinges on inequality (16): h(G) ≤ s_av+1, with equality iff G is strongly regular. This is not proved in the paper; it is imported via Remark 5.2 from [5, Theorem 2.14(a)] and [5, Theorem 2.30], where the first two authors of [5] overlap with the present authors. Lemma 5.3 correctly gives (s_av+1)(\\bar{s}_av+1)=n, so equality in the product forces equality in (16) for both G and its complement. Thus the entire equality characterization of strong regularity reduces to the correctness and exact equality condition of the imported theorem. Since the paper does not reproduce or independently verify that theorem, the central claim is only as secure as an external, overlapping-author result. This is a genuine soft spot: a misstated equality condition would make Theorem 5.4 false.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13280,"tokens_out":28387,"duration_ms":301651,"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":[{"comment":"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.","section":"Section 3, Theorem 3.7"},{"comment":"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.","section":"Corollary 3.8 and Example 3.5"},{"comment":"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.","section":"Section 5, Theorem 5.4 and Remark 5.2"},{"comment":"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.","section":"Section 5, Corollary 5.8"}],"minor_comments":[{"comment":"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.","section":"Section 3"},{"comment":"The claim about irregular graphs using average degree is unproved and unused. Consider removing it or providing a proof.","section":"After Lemma 5.3"},{"comment":"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.","section":"Theorem 3.7 proof"},{"comment":"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.","section":"Section 5, Theorem 5.4"}],"recommendation":"major_revision","confidential_remarks":"The reader's positive assessment misses real problems in Section 3. The proof of Theorem 3.7 uses a false identity, and Corollary 3.8 mixes up the Clebsch graph with its complement and L(K_6) with its complement; the listed graphs may be the right ones, but as written the statement and proof contradict each other. The central Theorem 5.4 is plausible, but it should be made self-contained with respect to (16), especially because that inequality is imported from overlapping-author work. I therefore recommend major revision rather than acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe main thing to know: this is a good, honest paper about Hoffman colorings of regular graphs. The genuinely new results are the geometric parametrization for strongly regular graphs (making the Hoffman number h = s+1), the finiteness theorem for bounded Hoffman number (Thm 3.7), the explicit h≤3 list (Cor 3.8), and the equality characterization in Thm 5.4: a regular graph G satisfies h(G)h(\\bar G) ≤ n with equality iff G is strongly regular. The vector-coloring application in Thm 4.1 is also a real improvement over [14].\n\nWhat the paper does well: the proofs are coherent and the authors are transparent about dependencies. They explicitly say the inequality in Thm 5.4 follows from the Lovász ϑ inequalities (18)(19), and they mention Roberson's equivalence with a lemma of his. That is fair credit. The geometric parametrization connects naturally to partial geometries, and the corollaries about Delsarte cliques and spreads are useful.\n\nThe soft spot is exactly where the stress-test note points: the 'only if' direction of Thm 5.4 uses inequality (16), h(G) ≤ s_av + 1 with equality iff strongly regular, which is imported from [5, Thm 2.14(a)] and [5, Thm 2.30]. The first two authors of [5] overlap with this paper, and the equality condition is not reproved here. If that imported claim is misstated, Thm 5.4 collapses. This is a genuine dependency, but it is a normal one: the paper states plainly that the theorem comes from [5] and why it applies. I would want a referee to verify that theorem's equality statement carefully before accepting. There are also minor notational slips (e.g., 'h(G)h(G)' in the intro should be h(G)h(\\bar G), and a sign issue in the proof of Thm 3.7) that should be cleaned up.\n\nOverall the paper holds up. The central argument is not circular; the geometric parameters are definitions, not fitted values. The main claims are new enough within the subfield, and the authors do not oversell them.\n\nWho is this for: researchers in spectral graph theory, especially those working on strongly regular graphs, Hoffman colorings, and the Lovász ϑ-number. It deserves a serious peer review, with the caveat about the imported theorem in mind. I would send it to a competent referee rather than desk reject it.","headline":"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].","tokens_in":13763,"tokens_out":4066,"would_cite":true,"duration_ms":37971,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C15","05E30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A product inequality involving the Hoffman bound characterizes strongly regular graphs among regular graphs.","keywords":["Hoffman bound","Hoffman coloring","strongly regular graphs","chromatic number","spectral graph theory","unique vector colorability","pseudo-geometric graphs","Neumaier graphs"],"falsifier":"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.","tokens_in":12928,"feed_emoji":"🎨","tokens_out":8976,"duration_ms":99789,"temperature":0.7,"pith_summary":"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.","feed_headline":"h(G)h(complement G) ≤ n pins down strong regularity","feed_subtitle":"The paper proves the product hits n exactly for strongly regular graphs, turning Hoffman's bound into a spectral test.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the average-parameter machinery and the inequality λmin(G) ≤ τ_av with equality iff strongly regular, the key input for Theorem 5.4.","marker":"[5]"},{"why":"Original source of the Hoffman bound, the quantity reinterpreted throughout as the Hoffman number h(G).","marker":"[22]"},{"why":"Hoffman's ratio bound for cocliques, from which the Hoffman bound for regular graphs and the notion of Hoffman cocliques are derived.","marker":"[20]"},{"why":"Background and standard results for strongly regular graphs, ratio/Delsarte bounds, pseudo-geometric parameters, and the classification of least eigenvalue −2 used in Corollary 3.8.","marker":"[8]"},{"why":"Lovász's theta-number inequalities give an alternative route to h(G)h(complement G) ≤ n and frame the remark that the equality characterization is new.","marker":"[24]"},{"why":"The vector-coloring result, Theorem 4.2, that Theorem 4.1 extends to Hoffman-colorable strongly regular graphs of type A.","marker":"[14]"},{"why":"Haemers' finiteness theorem for primitive strongly regular graphs with bounded chromatic number, strengthened by Theorem 3.7 to bounded Hoffman number.","marker":"[19]"},{"why":"Provides the characterization of non-core strongly regular graphs as Hoffman colorable with a Delsarte clique, used to identify the type A graphs covered by Theorem 4.1.","marker":"[28]"}],"fun_headline_variants":["Hoffman product ≤ n, equality means strongly regular","Strong regularity is the equality case of Hoffman product","Hoffman bound product saturates exactly for strongly regular graphs","Product of Hoffman numbers characterizes strongly regular graphs"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hoffman product ≤ n, equality means strongly regular","Strong regularity is the equality case of Hoffman product","Hoffman bound product saturates exactly for strongly regular graphs","Product of Hoffman numbers characterizes strongly regular graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000986,"raw_usage":{"total_tokens":3998,"prompt_tokens":704,"completion_tokens":3294,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":448,"completion_tokens_details":{"reasoning_tokens":3230}},"tokens_in":448,"tokens_out":3294,"duration_ms":24551,"temperature":1.0,"reasoning_tokens":3230,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T16:11:40.288507+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Abiad, B","cited_arxiv_id":null,"evidence_quote":"Supplies the average-parameter machinery and the inequality λmin(G) ≤ τ_av with equality iff strongly regular, the key input for Theorem 5.4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Original source of the Hoffman bound, the quantity reinterpreted throughout as the Hoffman number h(G)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Hoffman's ratio bound for cocliques, from which the Hoffman bound for regular graphs and the notion of Hoffman cocliques are derived."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Background and standard results for strongly regular graphs, ratio/Delsarte bounds, pseudo-geometric parameters, and the classification of least eigenvalue −2 used in Corollary 3.8."},{"cited_title":"Lov´ asz","cited_arxiv_id":null,"evidence_quote":"Lovász's theta-number inequalities give an alternative route to h(G)h(complement G) ≤ n and frame the remark that the equality characterization is new."},{"cited_title":"Godsil, D","cited_arxiv_id":null,"evidence_quote":"The vector-coloring result, Theorem 4.2, that Theorem 4.1 extends to Hoffman-colorable strongly regular graphs of type A."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Haemers' finiteness theorem for primitive strongly regular graphs with bounded chromatic number, strengthened by Theorem 3.7 to bounded Hoffman number."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the characterization of non-core strongly regular graphs as Hoffman colorable with a Delsarte clique, used to identify the type A graphs covered by Theorem 4.1."}],"review_version":1}