Research uncovers Turán numbers in non-bipartite graphs, revealing distinct extremal graph structures.
Let 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₀(H) such that ex(n, H)=e(Tn,k) and the Turán graph Tn,k is the only extremal graph provided n≥ n₀(H). A book graph Bᵣ₊₁ is a set of $r+1$ triangles with a common edge, where r≥0 is an integer. Note that Bᵣ₊₁ is a color-critical graph with χ(Bᵣ₊₁)=3. Simonovits' theorem implies that Tn,2 is the only extremal graph for Bᵣ₊₁-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ᵣ₊₁)=e(Tn,2) for n≥ n₀(Bᵣ₊₁)=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 Tn,2 is bipartite. Motivated by the above elegant results, we in this paper focus on the Turán problem of non-bipartite Bᵣ₊₁-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)≤(n-1)²4+1. For general r≥1, we determine the exact value of Turán number of Bᵣ₊₁ 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≥1.
No takes yet. Share an insight, caveat, or question.
Lu et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: