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

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án theorem, which implies that $G(r,s)$ is the $r$-partite Turán graph $T_{n,r}$ for $s\le 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\ge 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ö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].

12 pages, 5 figures