极值图论是图论的一个重要分支,主要研究图的全局属性与局部属性之间的关系。作为极值图论中最为经典和重要的问题之一,Tur\‘an 数问题自1941年由匈牙利数学家Tur\‘an提出以来,一直是图论、组合领域的热点问题之一。除了图论领域,Tur\‘an 理论的思想和研究方法在计算机科学、信息论、人工智能、数论、化学等其他学科领域也有着广泛的应用。 设 $\mathcal{F}$ 是图的一个集合,我们称图 $G$ 是 $\mathcal{F}$-禁止的,如果它不包含 $\mathcal{F}$ 中的任何元素作为子图。称一个 $n$ 顶点、$\mathcal{F}$-禁止的图的最大边数为$\mathcal{F}$ 的 Tur\‘an 数,记作 $ex(n, \mathcal{F})$。 更一般的,给定图$H$和图集$\mathcal{F}$,广义Tur\‘an 数$ex(n,H,\mathcal{F})$定义为$n$个顶点的$\mathcal{F}$-禁止的图中包含$H$数量的最大可能值。当$H = K_2$时,$ex(n,H,\mathcal{F}) = ex(n,\mathcal{F})$。本文主要研究 Tur\‘an 数以及与之相关的一些极值问题,主要研究成果如下: 我们确定了$n$个顶点、点色数小于等于3并且$C_4$-禁止的Tur\‘an 数的渐近界,解决了 Tait 和 Timmons 提出的问题;我们给出了$n$个顶点、点色数小于等于3的$\{C_3,C_4\}$-禁止的Tur\‘an 数的下界;我们还证明了,$n$个顶点的不含$C_5$和诱导的$C_4$作为子图的最大边数不超过$\frac{1}{\sqrt{6}}(1+o(1))n^\frac{3}{2}$,改进了Ergemlidze和Methuku的估计值。 对于广义Tur\‘an 数,我们给出了不含长奇圈的$n$点图中团$K_r$的数量的紧的上界,从而推广了Erd?s和Gallai的结论,也是对Luo最近结果的加强;我们确定了$ex(n,K_3,C_3^3)$的紧上界,并确定了$ex(n,K_3,P_3^3)$的精确值,并刻画达到这些界的图,其中$H^p$为$H$的边扩充图;我们还证明了$ ex(n,K_3,C_5)$不超过$\frac{1}{2\sqrt{6}}\left(1+o(1)\right)n^\frac{3}{2}$,这改进了Ergemlidze和Methuku的估计值。 最后我们确定了$n$个顶点的平面图中偶圈$C_{2k}$的最大可能值的渐近界,解决了Cox和Martin提出的猜想。
Extremal graph theory is an important branch of graph theory, mainly studying the relationship between the global properties and local substructure. Tur\‘an number, as one of the most classic and important problems in extremal graph theory, has been a hot topic in the fields of graph theory and combinatorics since it was proposed by Hungarian mathematician Tur\‘an in 1941. In addition to the field of graph theory, the research methods and ideas of Tur\‘an theory also have been widely used in other disciplines such as computer science, information theory, artificial intelligence, number theory, and chemistry. Let $\mathcal{F}$ be a set of graphs. A graph $G$ is $\mathcal{F}$-free if it does not contain any element of $\mathcal{F}$ as a subgraph. The Tur\‘an number of $\mathcal{F}$, denoted by $ex(n, \mathcal{F})$, is the maximum number of edges in a $\mathcal{F}$-free graph on $n$ vertices. More generally, given a graph $H$ and a set of graphs $\mathcal{F}$, the generalized Tur\‘an number $ex(n,H,\mathcal{F})$ is the maximum number of copies of $H$ in an $n$-vertex $\mathcal{F}$-free graph. Note that when $H = K_2$, $ex(n,H,\mathcal{F}) = ex(n,\mathcal{F})$. In this thesis, we mainly study the Tur\‘an number and some related extremal graph theory problems. The main results are as follows: We determine the asymptotic bound for the Tur\‘an number of $C_4$-free graphs with $n$ vertices and chromatic number at most 3, thereby resolving the problem posed by Tait and Timmons. We also give the lower bound for the Tur\‘an number of $\{C_3,C_4\}$-free graphs with $n$ vertices and chromatic number at most 3. Additionally, we show that the maximum number of edges in an induced-$C_4$-free and $C_5$-free graph on $n$ vertices is at most $\frac{1}{\sqrt{6}}(1+o(1))n^\frac{3}{2}$, improving an estimate of Ergemlidze and Methuku. Regarding generalized Tur\‘an numbers, we give the sharp upper bound for the number of cliques in graphs with bounded odd circumferences, thus extending the conclusions of Erd"os and Gallai and strengthening recent results by Luo. We also determine the sharp upper bound for $ex(n,K_3,C_3^3)$ and the exact value for $ex(n,K_3,P_3^3)$, and determine the graphs achieving these bounds, where $H^p$ denotes the edge blow-up graph of $H$. Furthermore, we prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $ \frac{1}{2\sqrt{6}}\left(1+o(1)\right)n^\frac{3}{2}$, improving an estimate of Ergemlidze and Methuku. Lastly, we resolve a conjecture of Cox and Martin by determining asymptotically the maximum number of copies of $C_{2k}$ in an $n$-vertex planar graph for every $k \geq 2$ .