Turán number of books in non-bipartite graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918126510145536 |
|---|---|
| author | Miao, Lu Liu, Ruifang van Dam, Edwin R. |
| author_facet | Miao, Lu Liu, Ruifang van Dam, Edwin R. |
| contents | Let $\mathrm{ex}(n, H)$ be the Turán number of $H$ for a given graph $H$. A graph is color-critical if it contains an edge whose removal reduces its chromatic number. Simonovits' chromatic critical edge theorem states that if $H$ is color-critical with $χ(H)=k+1$, then there exists an $n_0(H)$ such that ex$(n, H)=e(T_{n,k})$ and the Turán graph $T_{n,k}$ is the only extremal graph provided $n\geq n_0(H).$ A book graph $B_{r+1}$ is a set of $r+1$ triangles with a common edge, where $r\geq0$ is an integer. Note that $B_{r+1}$ is a color-critical graph with $χ(B_{r+1})=3$. Simonovits' theorem implies that $T_{n,2}$ is the only extremal graph for $B_{r+1}$-free graphs of sufficiently large order $n$. Furthermore, Edwards and independently Khadžiivanov and Nikiforov completely confirmed Erdős' booksize conjecture and obtained that ex$(n, B_{r+1})=e(T_{n,2})$ for $n\geq n_0(B_{r+1})=6r$. Recently, Zhai and Lin [J. Graph Theory 102 (2023) 502-520] investigated the problem of booksize from a spectral perspective.
Note that the extremal graph $T_{n,2}$ is bipartite. Motivated by the above elegant results, we in this paper focus on the Turán problem of non-bipartite $B_{r+1}$-free graphs of order $n$. For $r = 0,$ Erdős proved a nice result: If $G$ is a non-bipartite triangle-free graph on $n$ vertices, then $e(G)\leq\big\lfloor\frac{(n-1)^{2}}{4}\big\rfloor+1$. For general $r\geq1,$ we determine the exact value of Turán number of $B_{r+1}$ in non-bipartite graphs and characterize all extremal graphs provided $n$ is sufficiently large. An interesting phenomenon is that the Turán numbers and extremal graphs are completely different for $r=0$ and general $r\geq1.$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12578 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Turán number of books in non-bipartite graphs Miao, Lu Liu, Ruifang van Dam, Edwin R. Combinatorics 05C50, 05C35 Let $\mathrm{ex}(n, H)$ be the Turán number of $H$ for a given graph $H$. A graph is color-critical if it contains an edge whose removal reduces its chromatic number. Simonovits' chromatic critical edge theorem states that if $H$ is color-critical with $χ(H)=k+1$, then there exists an $n_0(H)$ such that ex$(n, H)=e(T_{n,k})$ and the Turán graph $T_{n,k}$ is the only extremal graph provided $n\geq n_0(H).$ A book graph $B_{r+1}$ is a set of $r+1$ triangles with a common edge, where $r\geq0$ is an integer. Note that $B_{r+1}$ is a color-critical graph with $χ(B_{r+1})=3$. Simonovits' theorem implies that $T_{n,2}$ is the only extremal graph for $B_{r+1}$-free graphs of sufficiently large order $n$. Furthermore, Edwards and independently Khadžiivanov and Nikiforov completely confirmed Erdős' booksize conjecture and obtained that ex$(n, B_{r+1})=e(T_{n,2})$ for $n\geq n_0(B_{r+1})=6r$. Recently, Zhai and Lin [J. Graph Theory 102 (2023) 502-520] investigated the problem of booksize from a spectral perspective. Note that the extremal graph $T_{n,2}$ is bipartite. Motivated by the above elegant results, we in this paper focus on the Turán problem of non-bipartite $B_{r+1}$-free graphs of order $n$. For $r = 0,$ Erdős proved a nice result: If $G$ is a non-bipartite triangle-free graph on $n$ vertices, then $e(G)\leq\big\lfloor\frac{(n-1)^{2}}{4}\big\rfloor+1$. For general $r\geq1,$ we determine the exact value of Turán number of $B_{r+1}$ in non-bipartite graphs and characterize all extremal graphs provided $n$ is sufficiently large. An interesting phenomenon is that the Turán numbers and extremal graphs are completely different for $r=0$ and general $r\geq1.$ |
| title | Turán number of books in non-bipartite graphs |
| topic | Combinatorics 05C50, 05C35 |
| url | https://arxiv.org/abs/2508.12578 |