For edge-color-critical graphs, non-$r$-partite spectral extremal graphs are edge extremal

Summary · qwen2.5:32b

The paper proves Fang and Lin's conjecture that non-$r$-partite spectral extremal graphs for edge-color-critical graph $F$ with $\chi(F)=r+1$ are also edge-extremal under specific conditions, including a hypothesis involving the Turán graph $T_{n,r}$ and an embeddability condition on $F$. For a specific case where $F=K_{1,1,t_3,\ldots,t_{r+1}}$, with each $t_i \ge 2$, it is shown that $\mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\lfloor n/r\rfloor+2(t_{\min}-1)$ for large $n$.

Suggested post angle

Discovering new results in graph theory can lead to advancements in graphics algorithms and optimization techniques.

Excerpt

arXiv:2607.00561v2 Announce Type: replace Abstract: A graph is non-$r$-partite if its chromatic number exceeds $r$. For an edge-color-critical graph $F$ with $\chi(F)=r+1$, let $\mathrm{ex}_{r+1,\rho}(n,F)$ be the maximum adjacency spectral radius among non-$r$-partite $F$-free graphs of order $n$, and let $\mathrm{EX}_{r+1,\rho}(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,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$ for every such $F$ and all large $n$. In this paper, we prove this inclusion under the hypothesis $\mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\lfloor n/r\rfloor+O(1)$, where $T_{n,r}$ is the Tur\'an graph, together with an embeddability condition on $F$. As the main application, for $F=K_{1,1,t_3,\ldots,t_{r+1}}$ with $t_3,\ldots,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$. We further identify the unique spectral extremal graph, so that in particular $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$.