pith. sign in

arxiv: 2605.14627 · v1 · pith:N42E3SDOnew · submitted 2026-05-14 · 🧮 math.CO

Spectral extremal results for triangle-free graphs with chromatic number at least four

Yinfen Zhu , Huiqiu Lin This is my paper

Pith reviewed 2026-06-30 20:53 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral radiusextremal graphstriangle-free graphschromatic numberGrötzsch graphblow-upsstability methods
0
0 comments X

The pith

For sufficiently large n, G(2,4) is a blow-up of the Grötzsch graph.

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

This paper determines the structure of G(2,4), the triangle-free graph on n vertices with chromatic number at least 4 that maximizes the spectral radius. It proves that this maximizer is uniquely a blow-up of the Grötzsch graph for all large enough n. The work extends earlier characterizations of G(2,3) and G(r,r+1) by applying stability methods to the new case. A sympathetic reader cares because the result gives an exact structural description and shows that the spectral maximizer coincides with the edge maximizer.

Core claim

We show that G(2,4) is precisely a blow-up of the Grötzsch graph for all sufficiently large n. This characterization is obtained by extending stability methods used for G(2,3) and G(r,r+1). Interestingly, under the same conditions, G(2,4) also coincides with the unique edge-extremal graph.

What carries the argument

G(2,4), the triangle-free n-vertex graph with chromatic number at least 4 maximizing the spectral radius, identified as the blow-up of the Grötzsch graph via extended stability arguments.

If this is right

  • The spectral extremal graph coincides with the unique edge-extremal graph under the same conditions.
  • The characterization holds for every sufficiently large n.
  • The result extends the spectral Turán theorem and the cases previously settled for smaller s.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same stability approach may identify blow-ups of other triangle-free high-chromatic graphs as extremal for larger chromatic numbers.
  • The observed coincidence between spectral and edge extremal graphs may hold for additional values of r and s.

Load-bearing premise

The stability methods from prior cases extend directly to chromatic number 4 for all large n without new exceptional graphs.

What would settle it

A triangle-free graph with chromatic number at least 4 on a large number of vertices whose spectral radius exceeds that of the blow-up of the Grötzsch graph of the same order would disprove the claim.

Figures

Figures reproduced from arXiv: 2605.14627 by Huiqiu Lin, Yinfen Zhu.

Figure 1
Figure 1. Figure 1: The graph F1. Theorem 1.1. ([18]) Let G be a graph on n vertices with n ≥ 150. If G is triangle-free and χ(G) ≥ 4, then e(G) ≤ (n − 3)2 4  + 5, with equality if and only if G = F1(n) up to isomorphism. Clearly, K3 is an odd cycle. For longer odd cycles, a result of Ren, Wang, Wang, and Yang implies that f(C2ℓ+1, 3) = ⌊ (n−2)2 4 ⌋ + 3 for ℓ ≥ 2 and n ≥ 318ℓ 2 ; see [17, Theorem 1.3]. The adjacency matrix … view at source ↗
Figure 2
Figure 2. Figure 2: The graph G. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The graphs F2 and F3. obtained from Kn−3−k 2 , n−3+k 2 by deleting 7 edges. Setting α1 = 0 and α2 = 7 in Lemma 2.2, we obtain |ρ(G) − ρ(Kn−3−k 2 , n−3+k 2 ) + 14 n | ≤ 0.1 n , which yields that ρ(G) ≤ ρ(Kn−3−k 2 , n−3+k 2 ) − 13.9 n ≤ n − 3 2 − 13.9 n . Combining this with Claim 3.9 yields ρ(G) ≤ n−3 2 − 13.8 n , which contradicts Claim 3.1. Case 2. V1({u2}) = ∅. It is straightforward to verify that G′ is … view at source ↗
read the original abstract

A graph is called $F$-free if it does not contain a copy of $F$. Let $G(r,s)$ denote a $K_{r+1}$-free graph of order $n$ with chromatic number at least $s$ that maximizes the spectral radius. Nikiforov [Linear Algebra Appl., 2007] proved the spectral Tur\'{a}n theorem, which implies that $G(r,s)$ is the $r$-partite Tur\'{a}n graph $T_{n,r}$ for $s\leq r$. Lin, Ning, and Wu [Combin. Probab. Comput., 2021] characterized the unique spectral extremal graph $G(2,3)$. This result was later extended by Li and Peng [SIAM J. Discrete Math., 2023] to all $s=r+1\geq 3$. In this paper, we push the characterization further by determining the unique extremal graph $G(2,4)$ for all sufficiently large $n$. Specifically, we show that $G(2,4)$ is precisely a blow-up of the Gr\"{o}tzsch graph. Interestingly, under the same conditions, $G(2,4)$ also coincides with the unique edge-extremal graph identified by Ren, Wang, Wang, and Yang [arXiv:2404.07486v2].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper characterizes the unique K_3-free n-vertex graph G with chromatic number at least 4 that maximizes the spectral radius, denoted G(2,4). Building on Nikiforov's spectral Turán theorem and prior characterizations of G(2,3) and G(r,r+1), it proves that for all sufficiently large n this extremal graph is a blow-up of the Grötzsch graph; the same graph is also the unique edge-extremal example from a concurrent arXiv preprint.

Significance. If the stability argument holds, the result supplies the first spectral characterization in the triangle-free, χ≥4 regime and demonstrates that the spectral and edge-extremal problems coincide in this setting. The extension of existing stability techniques to the Grötzsch blow-up supplies a concrete, parameter-free extremal graph and strengthens the link between spectral radius and chromatic number constraints.

minor comments (3)
  1. [Introduction / Theorem statement] The statement of the main theorem (presumably Theorem 1.1 or 1.2) should explicitly record the dependence of the 'sufficiently large n' threshold on the stability constants inherited from the cited G(2,3) and G(r,r+1) papers.
  2. [Preliminaries] Notation for the blow-up operation and the precise definition of the Grötzsch graph should be fixed once at the beginning rather than re-introduced in the stability section.
  3. [Section 3 or 4 (stability + eigenvalue comparison)] The spectral-radius comparison between the Grötzsch blow-up and other candidate triangle-free χ=4 graphs (e.g., Mycielski constructions of higher order) is only sketched; a short explicit inequality or reference to the eigenvalue formula would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive report, the accurate summary of our results, and the recommendation of minor revision. No specific major comments appear in the report, so we have no points requiring point-by-point rebuttal at this stage.

Circularity Check

0 steps flagged

No circularity; derivation extends prior stability results independently

full rationale

The paper determines the unique maximizer G(2,4) for large n by extending stability lemmas and spectral comparisons from the cited G(2,3) and G(r,r+1) characterizations. These prior results (including the Lin-Ning-Wu work with overlapping authorship) supply the base case and method, but the present argument applies them to the new chi >=4 triangle-free setting with fresh case analysis and asymptotic control; no equation reduces to a fitted parameter, self-defined quantity, or unverified self-citation chain. The coincidence with the edge-extremal graph from an independent arXiv preprint is noted but not used as a load-bearing premise. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no free parameters, axioms, or invented entities are identifiable from the given text.

pith-pipeline@v0.9.1-grok · 5778 in / 1081 out tokens · 32987 ms · 2026-06-30T20:53:10.299200+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 3 canonical work pages

  1. [1]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty, Graph Theory, Grad. Texts Math. 244, Springer, New York, 2008

    2008

  2. [2]

    Brouwer, Some lotto numbers from an extension of Tur´ an’s theorem, Afdeling Zuivere Wiskunde [Department of Pure Mathematics], 152.Mathematisch Centrum, Amsterdam,

    A.E. Brouwer, Some lotto numbers from an extension of Tur´ an’s theorem, Afdeling Zuivere Wiskunde [Department of Pure Mathematics], 152.Mathematisch Centrum, Amsterdam,

  3. [3]

    Chv´ atal, The minimality of the Mycielski graph, in:Graphs and combinatorics(Proc

    V. Chv´ atal, The minimality of the Mycielski graph, in:Graphs and combinatorics(Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Math., vol. 406, 1974, pp. 243–246. 11

    1973

  4. [4]

    Desai, L.Y

    D.N. Desai, L.Y. Kang, Y.T. Li, Z.Y. Ni, M. Tait, J. Wang, Spectral extremal graphs for intersecting cliques,Linear Algebra Appl.644(2022) 234–258

    2022

  5. [5]

    Fang, Y.T

    L.F. Fang, Y.T. Li, H.Q. Lin, J. Ma, Spectral supersaturation for color-critical graphs, arXiv:2512.22482v1

    work page arXiv

  6. [6]

    Guo, H.Q

    H.T. Guo, H.Q. Lin, Y.H. Zhao, A spectral condition for the existence of a pentagon in non-bipartite graphs,Linear Algebra Appl.627(2021) 140–149

    2021

  7. [7]

    B.L. Li, B. Ning, Eigenvalues and cycles of consecutive lengths,J. Graph Theory103 (2023), no. 3, 486–492

    2023

  8. [8]

    Y.T. Li, Y.J. Peng, Refinement on spectral Tur´ an’s theorem,SIAM J. Discrete Math.37 (2023), no. 4, 2462–2485

    2023

  9. [9]

    H.Q. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs,Combin. Probab. Comput. 30(2021), no. 2, 258–270

    2021

  10. [10]

    R.F. Liu, L. Miao, Spectral Tur´ an problem of non-bipartite graphs: forbidden books,Eu- ropean J. Combin.126(2025), Paper No. 104136, 18 pp

    2025

  11. [11]

    Nikiforov, Bounds on graph eigenvalues II,Linear Algebra Appl.427(2007), nos

    V. Nikiforov, Bounds on graph eigenvalues II,Linear Algebra Appl.427(2007), nos. 2-3, 183–189

    2007

  12. [12]

    Nikiforov, A spectral condition for odd cycles in graphs,Linear Algebra Appl.428(2008), no

    V. Nikiforov, A spectral condition for odd cycles in graphs,Linear Algebra Appl.428(2008), no. 7, 1492–1498

    2008

  13. [13]

    Nikiforov, Stability for large forbidden subgraphs,J

    V. Nikiforov, Stability for large forbidden subgraphs,J. Graph Theory62(2009), no. 4, 362–368

    2009

  14. [14]

    Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl.432(2010), no

    V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl.432(2010), no. 9, 2243–2256

    2010

  15. [15]

    B. Ning, X. Peng, Extensions of the Erd˝ os-Gallai theorem and Luo’s theorem,Comb. Probab. Comput.29(2020), no. 1, 128–136

    2020

  16. [16]

    Nosal, Eigenvalues of Graphs (Master’s thesis), University of Calgary, 1970

    E. Nosal, Eigenvalues of Graphs (Master’s thesis), University of Calgary, 1970

    1970

  17. [17]

    S.J. Ren, J. Wang, S.P. Wang, W.H. Yang, A stability result forC 2k+1-free graphs,SIAM J. Discrete Math.38(2024), no. 2, 1733–1756

    2024

  18. [18]

    S.J. Ren, J. Wang, S.P. Wang, W.H. Yang, Extremal triangle-free graphs with chromatic number at least four, arXiv:2404.07486v2

    work page arXiv

  19. [19]

    Tur´ an, On an extremal problem in graph theory,Mat

    P. Tur´ an, On an extremal problem in graph theory,Mat. Fiz. Lapok48(1941) 436–452

    1941

  20. [20]

    Zhai, H.Q

    M.Q. Zhai, H.Q. Lin, A strengthening of the spectral chromatic critical edge theorem: books and theta graphs,J. Graph Theory102(2023), no. 3, 502–520

    2023

  21. [21]

    Zhang, Y.H

    Z.Y. Zhang, Y.H. Zhao, A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs,Discrete Math.346(2023), no. 6, Paper No. 113365, 10 pp

    2023

  22. [22]

    Zou, Y.T

    L.T. Zou, Y.T. Li, Y.J. Peng, Strong spectral stabilities forC 2k+1-free graphs, arXiv:2508.13643v2. 12

    work page arXiv