This is the homepage of the SUSTech Discrete Mathematics Seminar at the Department of Mathematics at SUSTech.
Speaker: Ruifang Liu (Zhengzhou University)
Room: College of Science M4009
Time: 10:00 - 11:00
Tencent Meeting: 526 396 130
Let ex$(n, H)$ be the Tur'{a}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'{a}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\v{z}iivanov and Nikiforov completely confirmed Erd\H{o}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'{a}n problem of non-bipartite $B_{r+1}$-free graphs of order $n$. For $r = 0,$ Erd\H{o}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'{a}n number of $B_{r+1}$ in non-bipartite graphs and characterize all extremal graphs provided $n$ is sufficiently large.
tags: