Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.12210 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913995365023744 |
|---|---|
| author | Wang, Bing Chen, Wenwen Zhang, Ping |
| author_facet | Wang, Bing Chen, Wenwen Zhang, Ping |
| contents | The classical Simonovits' chromatic critical edge theorem shows that for sufficiently large $n$, if $H$ is an edge-color-critical graph with $χ(H)=p+1\ge 3$, then the Turán graph $T_{n,p}$ is the unique extremal graph with respect to ${\rm ex}(n,H)$. Denote by ${\rm EX}_{r+1}(n,H)$ and ${\rm SPEX}_{r+1}(n,H)$ the family of $n$-vertex $H$-free non-$r$-partite graphs with the maximum size and with the spectral radius, respectively. Li and Peng [SIAM J. Discrete Math. 37 (2023) 2462--2485] characterized the unique graph in $\mathrm{SPEX}_{r+1}(n,K_{r+1})$ for $r\geq 2$ and showed that $\mathrm{SPEX}_{r+1}(n,K_{r+1})\subseteq \mathrm{EX}_{r+1}(n,K_{r+1})$. It is interesting to study the extremal or spectral extremal problems for color-critical graph $H$ in non-$r$-partite graphs. For $p\geq 2$ and $q\geq 1$, we call the graph $B_{p,q}:=K_p\nabla qK_1$ a complete split graph (or generalized book graph). In this note, we determine the unique spectral extremal graph in $\mathrm{SPEX}_{r+1}(n,B_{p,q})$ and show that $\mathrm{SPEX}_{r+1}(n,B_{p,q})\subseteq \mathrm{EX}_{r+1}(n,B_{p,q})$ for sufficiently large $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12210 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Non-r-partite graphs without complete split subgraphs Wang, Bing Chen, Wenwen Zhang, Ping Combinatorics Spectral Theory The classical Simonovits' chromatic critical edge theorem shows that for sufficiently large $n$, if $H$ is an edge-color-critical graph with $χ(H)=p+1\ge 3$, then the Turán graph $T_{n,p}$ is the unique extremal graph with respect to ${\rm ex}(n,H)$. Denote by ${\rm EX}_{r+1}(n,H)$ and ${\rm SPEX}_{r+1}(n,H)$ the family of $n$-vertex $H$-free non-$r$-partite graphs with the maximum size and with the spectral radius, respectively. Li and Peng [SIAM J. Discrete Math. 37 (2023) 2462--2485] characterized the unique graph in $\mathrm{SPEX}_{r+1}(n,K_{r+1})$ for $r\geq 2$ and showed that $\mathrm{SPEX}_{r+1}(n,K_{r+1})\subseteq \mathrm{EX}_{r+1}(n,K_{r+1})$. It is interesting to study the extremal or spectral extremal problems for color-critical graph $H$ in non-$r$-partite graphs. For $p\geq 2$ and $q\geq 1$, we call the graph $B_{p,q}:=K_p\nabla qK_1$ a complete split graph (or generalized book graph). In this note, we determine the unique spectral extremal graph in $\mathrm{SPEX}_{r+1}(n,B_{p,q})$ and show that $\mathrm{SPEX}_{r+1}(n,B_{p,q})\subseteq \mathrm{EX}_{r+1}(n,B_{p,q})$ for sufficiently large $n$. |
| title | Non-r-partite graphs without complete split subgraphs |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2508.12210 |