A reduction principle for non-$r$-partite spectral extremal problems, with a complete multipartite classification

Abstract

A graph is non-$r$-partite if its chromatic number exceeds $r$. For an edge-color-critical graph $F$ with $\ddot{I}‡(F)=r+1$, let ${\mathrm{ex}}_{r+1,\ddot{I}}(n,F)$ be the maximum adjacency spectral radius among non-$r$-partite $F$-free graphs of order $n$, and let ${\mathrm{EX}}_{r+1,\ddot{I}}(n,F)$ and ${\mathrm{EX}}_{r+1}(n,F)$ be the families of such graphs attaining, respectively, this maximum spectral radius and the maximum number of edges ${\mathrm{ex}}_{r+1}(n,F)$. Fang and Lin conjectured that ${\mathrm{EX}}_{r+1,\ddot{I}}(n,F)\subseteq {\mathrm{EX}}_{r+1}(n,F)$ for every such $F$ and all large $n$. We prove a reduction principle: if $F$ is \emph{$s$-embeddable} and ${\mathrm{ex}}_{r+1}(n,F)=|E(T_{n,r})|-\lfloor n/r\rfloor +2(s-1)$, where $T_{n,r}$ is the Turán graph, then the inclusion holds and, moreover, the spectral extremal graph is unique. The reduction replaces the spectral problem by an edge-counting one, and its proof rests on a direct comparison of secular functions together with a second-order residual refinement of the Rayleigh principle. We then determine the spectral extremal graphs for all edge-color-critical complete multipartite forbidden graphs. For $F=K_{1,1,t_3,\dots ,t_{r+1}}$ with $t_3,\dots ,t_{r+1}\ge 2$ we show \[ \mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\Bigl\lfloor\frac nr\Bigr\rfloor+2(t_{\min}-1), \qquad t_{\min}:=\min\{t_3,\ldots,t_{r+1}\}, \] for all sufficiently large $n$, and we identify the unique spectral extremal graph; in particular ${\mathrm{EX}}_{r+1,\ddot{I}}(n,F)\subseteq {\mathrm{EX}}_{r+1}(n,F)$. The endpoint $t_3=1$ lies outside the embeddability framework and is treated by a separate argument: for $F=K_{1,1,1,t_4,\dots ,t_{r+1}}$ with $r\ge 3$, the unique non-$r$-partite spectral extremal graph is $Y_r(n)$, obtained through a saturation reduction followed by the spectral refinement of Turán's theorem. The complete graph $K_{r+1}$ and the complete split graph $B_{r,q}$

40 pages

Topics & keywords