BIMSA >
Graphs: Structure, Spectra, and Extremes
Graphs: Structure, Spectra, and Extremes
Turán number of books in non-bipartite graphs
Turán number of books in non-bipartite graphs
Organizer
Speaker
Ruifang Liu
Time
Friday, August 28, 2026 4:00 PM - 5:00 PM
Venue
A3-4-301
Online
Zoom 537 192 5549
(BIMSA)
Abstract
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 $\chi(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 $\chi(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$.
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.
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.
Speaker Intro
刘瑞芳，郑州大学数学与统计学院教授，博士生导师，河南省高层次人才。中原基础研究领军人才，河南省杰青，河南省教育厅学术技术带头人，中国工业与应用数学学会图论组合及应用专业委员会常务委员。主要从事代数图论与极值图论的研究工作。在《Journal of Graph Theory》、《European Journal of Combinatorics》、《Electronic Journal of Combinatorics》、《Advances in Applied Mathematics》等图论组合重要期刊发表SCI学术论文70余篇。主持国家自然科学基金项目多项，中原英才计划1项。曾在美国西弗吉尼亚大学数学系和香港浸会大学数学系进行学术访问。