关于奇圈稳定性问题的一个注记

doi:10.12677/AAM.2022.112085

期刊菜单

关于奇圈稳定性问题的一个注记
A Note on Stability of Odd Cycles

DOI: 10.12677/AAM.2022.112085, PDF, HTML, XML, 下载: 335 浏览: 524
作者: 袁小利, 王健：太原理工大学，数学学院，山西太原
关键词: Tur?n数；稳定性；奇圈；Tur?n Number； Stability； Odd Cycles

摘要: 令C_2k−1是含有2k−1个顶点的图，如果图G不包含图C2k−1作为子图，那么称图G是C_2k−1禁止的。本文中，我们证明了对于任意一个n个顶点的图G，如果G是C_2k−1禁止的且

，那么当n充分大时，图G至多删除260δ²n²条边就可以变为一个二部图。

Abstract: Let C_2k−1 be a cycle of length 2k − 1. A graph G is called C_2k−1-free if G does not contain C_2k−1 as a subgraph. In this paper, we show that if G is a C_2k−1-free graph on n vertices with

edges, then G can be made bipartite by deleting at most edges for n sufficiently large.

文章引用：袁小利, 王健. 关于奇圈稳定性问题的一个注记[J]. 应用数学进展, 2022, 11(2): 804-810. https://doi.org/10.12677/AAM.2022.112085

1. 引言

给定两个简单图G和F，如果图G不包含图F作为子图，那么称图G是F禁止的。令 $e x (n, F)$ 表示n个顶点的F禁止图G含有的最大边数。1941年，Turάn [1] 证明了n个顶点K_r₊₁禁止的图的最大边数为Turάn图的边数，Turάn图是每个部集大小为 $⌈ \frac{n}{r} ⌉$ 或 $⌊ \frac{n}{r} ⌋$ 的平衡r部完全图，记为 $T_{r} (n)$ ， $e (T_{r} (n)) = t_{r} (n)$ 。这一重要结论即为极值图论中著名的Turάn定理。在Turάn定理的基础上，Erdős [2] 和Simonovits [3] 进一步证明了如果图G是K_r₊₁禁止的，且满足 $e (G) = t_{r} (n) - o (n^{2})$ ，那么图G可以通过添加或删除 $o (n^{2})$ 条边后变为r部Turάn图。1981年，Brouwer [4] 证明了任意一个K_r₊₁禁止的图G， $e (G) \geq t_{r} (n) - ⌊ \frac{n}{r} ⌋$ ，那么图G为一个r部图。这一类有趣的问题被称为Turάn定理的稳定性问题，目前已经得到了广泛的研究和应用，相关文献可查阅 [5] - [12]。

1966年，Erdős [2] 证明了下面的Erdős-Stone-Simonovits定理。

定理1.1对于任意给定的一个图H，

$(1 - \frac{1}{χ (H) - 1} - o (1)) \frac{n^{2}}{2} \leq e x (n, H) \leq (1 - \frac{1}{χ (H) - 1} + o (1)) \frac{n^{2}}{2} .$

令 $f_{r} (n, t)$ 表示为使得满足对于任意一个含有 $t_{r} (n) - t$ 条边的K_r₊₁禁止的图G通过删掉至多 $f_{r} (n, t)$ 条边后成为r部图的最小值。2013年，Füredi [13] 首先证明了 $f_{r} (n, t) \leq t$ 。当 $t \leq δ_{r} n^{2}$ 时，Roberts和Scott [14] 证明了 $f_{r} (n, t) = O (t^{3 / 2} / n)$ 。后来，Balogh，Clemen，Lavrov，Lidický和Pfender [15] 确定了 $f_{r} (n, t)$ 的一个渐进的界，并提出了下面的一个关于精确界的猜想。

猜想1.1令 $r \geq 2$ ，n是一个充分大的正整数。对于任意一个含n个顶点K_r₊₁禁止的图G，存在一个不平衡的 $C_{5} \lor K_{r - 2}$ 的blow-up图H，满足 $e (H) \geq e (G), D_{r} (H) \geq D_{r} (G)$ 。

令G为k个顶点的图，图G的blow-up图 $H = G [n_{1}, \dots, n_{k}]$ ， $V (H) = \cup_{i \in [k]} W_{i}$ ，其中 $| W_{i} | = n_{i}$ ， $W_{i}$ 是两两不相交的。如果 $w \in W_{i}$ 与 $w^{'} \in W_{j}$ 在图H中是相邻的当且仅当 $v_{i}$ 和 $v_{j}$ 在图G中是相邻的。我们用 $D_{r} (G)$ 表示图G成为r部图需要删掉的最少边数。令 $Z, Z_{3}, \dots, Z_{r}$ 为一个完全 $(r - 1)$ 部图的 $r - 1$ 个部集，其中Z由一个C₅的blow-up图构成 $(Z = X \cup Y_{1} \cup Y_{2} \cup Z_{1} \cup Z_{2})$ 。如果 $| X | \leq | Y_{1} | = | Y_{2} | \leq | Z_{i} |$ ，并且 $X \cup Y_{1} \cup Z_{1}, X \cup Y_{2} \cup Z_{2}, Z_{3}, \dots, Z_{r}$ 每个部集大小为 $⌊ \frac{n + | X |}{r} ⌋$ 或 $⌈ \frac{n + | X |}{r} ⌉$ ，那么我们称这个图为星Turάn图。2020年，Korάndi，Roberts和Scott [16] 证明了Balogh [15] 他们提出的猜想1.1，证明了下面的定理1.2。

定理1.2令 $r \geq 2$ ， $δ_{r} > 0$ ，如果图G是含n个顶点K_r₊₁禁止的， $e (G) \geq t_{r} (n) - δ_{r} n^{2}$ ，那么存在一个含n个顶点的星Turάn图 $G^{*}$ ，满足 $e (G^{*}) \geq e (G), D_{r} (G^{*}) \geq D_{r} (G)$ 。

另外，他们在论文中还提出了一个关于奇圈Turάn问题稳定性的猜想。

猜想1.2令 $k \geq 1$ ，图G是含n个顶点不包含C_2k−1禁止的， $e (G) \geq (1 / 4 - δ) n^{2}$ ，那么一定存在一个C_2k+1的blow-up图 $G^{*}$ ，满足 $e (G^{*}) \geq e (G), D_{2} (G^{*}) \geq D_{2} (G)$ 。

在本文中，我们证明了下面的定理。

定理1.3令 $k \geq 2$ ， $0 < δ \leq k^{- 20}$ ， $n \geq 10 k^{30}$ ，图G为含n个顶点的C_2k−1禁止的图， $e (G) \geq \frac{n^{2}}{4} - δ n^{2}$ ，那么 $D_{2} (G) \leq 260 δ^{2} n^{2}$ 。

下面我们给出本文中的一些相关定义。在简单图G中，我们用 $\deg (v)$ 表示图G中顶点v的度数，为了方便起见，我们用 $d (v)$ 代替 $\deg (v)$ ， $δ (G)$ 表示图G的最小度数， $χ (G)$ 表示图G的色数，对于G的顶点子集 $X \subseteq V (G)$ ，用 $G [X]$ 表示由顶点子集合X生成的导出子图，令 $G - X$ 表示由 $V (G) \ X$ 生成的导出子图。 $N_{G} (X)$ 表示G中与X的某个顶点相邻的所有顶点集。设 $X, Y \subseteq V (G)$ 且 $X \cap Y = \emptyset$ ，令 $G [X, Y]$ 表示G的一个特定子图，其顶点集合为 $X \cup Y$ ，边集合为所有一个端点在X中另一个端点在Y中的所有G中边构成的集合。令 $G_{1}$ 与 $G_{2}$ 为两个顶点不相交的图， $G_{1} + G_{2}$ 为顶点集为 $V (G_{1}) + V (G_{2})$ ，边集为 $E (G_{1}) + E (G_{2})$ 的图。 $G_{1} \lor G_{2}$ 表示在图 $G_{1} + G_{2}$ 中，把 $G_{1}$ 与 $G_{2}$ 的每个顶点连接起来所得到的图。

2. 证明定理1.3

图G是含n个顶点C_2k−1禁止的图， $e (G) \geq \frac{n^{2}}{4} - δ n^{2}$ ，我们的目标是确定 $D_{2} (G)$ 的一个上界。如果直接在图G中确定 $D_{2} (G)$ 的一个上界是比较困难的，所以我们考虑首先在图G中寻找一个足够大的 $C_{3}, C_{5}, C_{2 k - 1}$ 禁止的子图 $G^{'}$ ，确定 $D_{2} (G^{'})$ 的一个上界，然后进一步确定 $D_{2} (G)$ 的一个上界。在证明过程中我们需要下面的一些相关结论。

定理2.1 [Fox, Himwich, Mani [17] ] G为含n个顶点的C_2k−1禁止的图， $e (G) \geq \frac{n^{2}}{4} - δ n^{2}$ ，那么图G可以通过删掉 $100 k^{4} n^{3 / 2}$ 条边后变成一个 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的图。

引理2.1 [Andrάsfai, Erdős, Sós [18] ] G是含n个顶点图， $χ (G) \geq 3$ ，如果图G中的最短奇圈圈长为 $2 k + 1$ ，那么 $δ (G) \leq \frac{2 n}{2 k + 1}$ 。

如果G是含n个顶点的 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的图，那么图G的最短奇圈圈长至少为 $2 k + 1$ ，根据引理2.1知，当图G的最小度满足 $δ (G) > \frac{2}{2 k + 1} n$ 时，那么图G为一个二部图。

引理2.2 G为含n个顶点的 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的图， $e (G) \geq \frac{n^{2}}{4} - ε n^{2}$ ，那么存在顶点子集 $S \subseteq G$ ， $| S | \leq 16 ε n$ ，使得 $G - S$ 为一个二部图，并且

$e (G - S) \geq \frac{n^{2}}{4} - 7 ε n^{2}, δ (G - S) \geq \frac{1}{2 k + 1} (1 - 16 ε) n .$

证明：令 $G_{0} = G$ ，每次删掉一个顶点，依次形成图 $G_{0}, G_{1}, \dots, G_{l}$ ， $| G_{i} | = n_{i} = n - i$ 。如果 $G_{i}$ 中存在一个顶点v，满足 $d (v) \leq \frac{2}{2 k + 1} (n - i)$ ，那么我们令 $G_{i + 1} = G_{i} - v$ ，继续上述删点过程。否则，如果 $G_{i}$ 中任意一点 $v \in V (G_{i})$ ，满足 $d (v) > \frac{2}{2 k + 1} (n - i)$ ，那么停止删点过程。

令S表示上述删点过程图G中删掉的所有顶点集合， $G - S = G_{l}$ ， $n_{l} = V (G - S)$ 。 $G - S$ 是含 $n_{l}$ 个顶点的 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的图，那么图 $G - S$ 的最小奇圈圈长至少为 $2 k + 1$ ，再由删点过程知 $δ (G - S) > \frac{2}{2 k + 1} n_{l}$ 。根据引理2.1我们得到图 $G - S$ 为二部图。

因为 $G - S$ 是 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的图，所以 $e (G - S) \leq \frac{n_{l}^{2}}{4}$ 。那么

$\begin{matrix} \frac{n_{l}^{2}}{4} \geq e (G - S) \geq e (G) - \frac{2}{2 k + 1} \sum_{i = n_{l} + 1}^{n} i \\ \frac{n_{l}^{2}}{4} \geq (\frac{1}{4} - ε) n^{2} - \frac{2}{2 k + 1} \frac{(n_{l} + 1 + n) (n - n_{l})}{2} \\ \frac{n_{l}^{2}}{4} \geq (\frac{1}{4} - ε) n^{2} - \frac{1}{2 k + 1} (n^{2} - n_{l}^{2} + n - n_{l}) \\ \frac{2 k - 3}{4 (2 k + 1)} n_{l}^{2} \geq \frac{2 k - 3}{4 (2 k + 1)} n^{2} - ε n^{2} - \frac{1}{2 k + 1} (n - n_{l}) \\ ε n^{2} \geq \frac{2 k - 3}{4 (2 k + 1)} (n^{2} - n_{l}^{2}) - \frac{1}{2 k + 1} (n - n_{l}) \end{matrix}$ (2.1)

如果 $n_{l} < \frac{n}{2}$ ，那么

$\frac{2 k - 3}{4 (2 k + 1)} (n^{2} - n_{l}^{2}) - \frac{1}{2 k + 1} (n - n_{l}) > \frac{3 (2 k - 3)}{16 (2 k + 1)} n^{2} - \frac{n}{2 k + 1} \geq \frac{3 (2 k - 3)}{32 (2 k + 1)} n^{2} > ε n^{2} .$

得到矛盾，因此 $n_{l} \geq \frac{n}{2}$ ，令

$f (x) = \frac{2 k - 3}{4 (2 k + 1)} x^{2} - \frac{x}{2 k + 1},$

由拉格朗日中值定理得，存在某个整数 $ξ \in (n_{l}, n)$ ，使得

$\begin{matrix} f (n) - f (n_{l}) = f^{'} (ξ) (n - n_{l}) \\ = (\frac{2 k - 3}{2 (2 k + 1)} ξ - \frac{1}{2 k + 1}) (n - n_{l}) . \end{matrix}$

由于 $ξ \geq n_{l} \geq \frac{n}{2}$ ，

$\begin{matrix} f (n) - f (n_{l}) \geq (\frac{2 k - 3}{4 (2 k + 1)} n - \frac{1}{2 k + 1}) (n - n_{l}) \\ \geq \frac{2 k - 3}{8 (2 k + 1)} n (n - n_{l}) . \end{matrix}$ (2.2)

根据(2.1) (2.2)式得， $ε n^{2} \geq \frac{2 k - 3}{8 (2 k + 1)} n (n - n_{l})$ ，由此推出 $n_{l} \geq (1 - 16 ε) n$ ，因为 $n_{l} = V (G - S)$ ，那么 $| S | = n - n_{l} \leq 16 ε n$ ，并且

$\begin{matrix} e (G - S) \geq e (G) - (\frac{2}{2 k + 1} n) | S | \geq \frac{n^{2}}{4} - 7 ε n^{2}, \\ δ (G - S) \geq \frac{2}{2 k + 1} n_{l} \geq \frac{2}{2 k + 1} (1 - 16 ε) n . \end{matrix}$

引理2.2即证。

定理1.3的证明：根据定理2.1知，存在一个子图 $G^{'} \subseteq G$ ，使得图 $G^{'}$ 是 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的，且 $V (G^{'}) = V (G) = n$ ，令 $ε = 2 δ$ ，因为 $n \geq 10 k^{30}$ ，那么

$e (G^{'}) \geq \frac{n^{2}}{4} - δ n^{2} - 100 k^{4} n^{3 / 2} \geq \frac{n^{2}}{4} - 2 δ n^{2} = \frac{n^{2}}{4} - ε n^{2} .$

再根据引理2.2知，图 $G^{'}$ 中存在一个顶点子集 $T \subseteq V (G^{'})$ ， $| T | \leq 16 ε n$ ，使得 $G^{'} - T$ 为一个二部图，并且

$e (G^{'} - T) \geq \frac{n^{2}}{4} - 7 ε n^{2}, δ (G^{'} - T) \geq \frac{2}{2 k + 1} (1 - 16 ε) n .$

令A，B为二部图 $G^{'} - T$ 的两个部集。因为

$δ (G^{'} - T) \geq \frac{2}{2 k + 1} (1 - 16 ε) n,$

所以 $| A |, | B | \geq \frac{2}{2 k + 1} (1 - 16 ε) n$ ，又因为 $| A | + | B | \leq n$ ，所以得到 $| A |, | B | \leq (1 - \frac{2 + 32 ε}{2 k + 1}) n$ 。

断言2.1任意一个顶点 $u \in T$ ， $N_{A} (u) = \emptyset$ 或 $N_{B} (u) = \emptyset$ 。

证明断言2.1若不然，我们假设 $N_{A} (u) \neq \emptyset$ 且 $N_{B} (u) \neq \emptyset$ ，那么一定存在两个顶点，不妨设为 $x, y$ ，使得满足 $x \in N_{A} (u), y \in N_{B} (u)$ 。根据引理2.2知

$δ_{G^{'} - T} (x) \geq \frac{2}{2 K + 1} (1 - 16 ε) n; | A |, | B | \geq \frac{2}{2 k + 1} (1 - 16 ε) n .$

利用贪婪算法我们一定可以在图 $G^{'} - T$ 中找到一条长为 $2 k - 6$ 起点为 $x$ 终点为 $x^{'}$ 的路 $P_{x x^{'}}$ ，因为 $G^{'} - T$ 为二部图， $P_{x x^{'}}$ 为偶长路，所以 $x^{'} \in A$ ，由于

$d_{B} (x^{'}), d_{A} (y) \geq \frac{2}{2 k + 1} (1 - 16 ε) n,$

那么

$| N_{A \ P_{x x^{'}}} (y) |, | N_{B \ P_{x x^{'}}} (x^{'}) | \geq \frac{2}{2 k + 1} (1 - 16 ε) n - (k - 2) .$

我们断言 $e (N_{A \ P_{x x^{'}}} (y), N_{B \ P_{x x^{'}}} (x^{'})) \neq 0$ 。若不然，如果 $e (N_{A \ P_{x x^{'}}} (y), N_{B \ P_{x x^{'}}} (x^{'})) = 0$ ，那么

$\begin{matrix} \bar{e} (N_{A \ P_{x x^{'}}} (y), N_{B \ P_{x x^{'}}} (x^{'})) \geq {(2 / (2 k + 1) (1 - 16 ε) n - (k - 2))}^{2} \\ \geq \frac{3}{{(2 k + 1)}^{2}} {(1 - 16 ε)}^{2} n^{2} . \end{matrix}$ (2.3)

又因为 $e (G^{'} - T) \geq \frac{n^{2}}{4} - 7 ε n^{2}$ ，所以

$\begin{matrix} \bar{e} (N_{A \ P_{x x^{'}}} (y), N_{B \ P_{x x^{'}}} (x^{'})) \leq \bar{e} (G^{'} - T) \\ \leq \frac{n^{2}}{4} - e (G^{'} - T) \\ \leq 7 ε n^{2} \end{matrix}$ (2.4)

根据(2.3) (2.4)得 $\frac{3}{{(2 k + 1)}^{2}} {(1 - 16 ε)}^{2} n^{2} \leq 7 ε n^{2}$ ，由此推出 $ε > \frac{1}{3 {(2 k + 1)}^{2} + 96}$ ，这与定理条件 $ε = 2 δ \leq 2 k^{- 20}$ 矛盾，所以我们的假设不成立，即 $e (N_{A \ P_{x x^{'}}} (y), N_{B \ P_{x x^{'}}} (x^{'})) \neq 0$ 。

不妨设存在一条边 $a b \in e (N_{A \ P_{x x^{'}}} (y), N_{B \ P_{x x^{'}}} (x^{'}))$ ， $a \in N_{A \ P_{x x^{'}}} (y)$ ， $b \in e (N_{B \ P_{x x^{'}}} (x^{'}))$ 。在这种情况下，我们得到 $u P_{x x^{'}} b a y u$ 为一个 $2 k - 1$ 长的圈，这与图 $G^{'}$ 是不包含C_2k−1的条件矛盾，所以对于任意一个顶点 $u \in T, N_{A} (u) = \emptyset, N_{B} (u) = \emptyset$ ，断言2.1即证。

根据断言2.1知，顶点子集T中的所有顶点与A或B中至少一个部集之间不连边。下面我们考虑将顶点子集合T中的所有顶点重新放入 $G^{'}$ 任意一点 $u \in T$ ，如果 $N_{A} (u) = \emptyset$ ，那么我们将顶点u放入A中。反之，如果 $N_{B} (u) = \emptyset$ ，那么我们将顶点u放入B中。顶点子集T中所有顶点放入A，B之后，我们最终得到了图 $G^{'}$ 的一个二部划分，令其为 $V_{1}, V_{2}$ ， $A \subseteq V_{1}$ ， $B \subseteq V_{2}$ 。即

$\forall u \in T \cap V_{1}, | N (u) \cap A | = \emptyset; \forall v \in T \cap V_{2}, | N (v) \cap B | = \emptyset .$

令 $T_{1} = T \cap V_{1}$ ， $T_{2} = T \cap V_{2}$ ， $H = G^{'} [T_{1}] \cup G^{'} [T_{2}]$ ，根据T中顶点的放入原则，我们知道图 $G^{'}$ 的二部划分中每个部集的内部的边只与 $T_{1}, T_{2}$ 相关联，所以

$D_{2} (G^{'}) \leq e (H)$ 。

因为 $G^{'}$ 是C_2k−1禁止的，所以 $G^{'} [T_{1}]$ 和 $G^{'} [T_{2}]$ 也是C_2k−1禁止的，所以

$e (G^{'} [T_{1}]) \leq \frac{{| T_{1} |}^{2}}{4}, e (G^{'} [T_{2}]) \leq \frac{{| T_{2} |}^{2}}{4} .$

所以

$\begin{matrix} e (H) = e (G^{'} [T_{1}]) + e (G^{'} [T_{2}]) \\ \leq \frac{{| T_{1} |}^{2}}{4} + \frac{{| T_{2} |}^{2}}{4} \\ \leq \frac{{| T_{1} \cup T_{2} |}^{2}}{4} = \frac{{| T |}^{2}}{4} . \end{matrix}$

由于 $D_{2} (G^{'}) \leq e (H)$ ， $| T | \leq 16 ε n$ ，所以

$D_{2} (G^{'}) \leq e (H) \leq 64 ε^{2} n^{2} .$

这一结果表明含n个顶点的 $C_{3}, C_{5}, \dots, C_{2 k - 1}$ 禁止的图 $G^{'}$ ， $e (G^{'}) \geq (\frac{1}{4} - ε) n^{2}$ ， $D_{2} (G^{'}) \leq 64 ε^{2} n^{2}$ 。又因为n是充分大的， $e (G) \geq e (G^{'}) + 100 k^{4} n^{3 / 2}$ ， $ε = 2 δ$ ， $n \geq 100 k^{30}$ ，所以有

$D_{2} (G) \leq D_{2} (G^{'}) + 100 k^{4} n^{3 / 2} \leq 64 ε^{2} n^{2} + ε^{2} n^{2} \leq 65 ε^{2} n^{2} \leq 260 δ^{2} n^{2} .$

定理1.3即证。

3. 结语

本文主要对奇圈Turάn问题的稳定性进行了研究。对于任意一个C_2k−1禁止的图G， $e (G) \geq \frac{1}{4} n^{2} - δ n^{2}$ ，我们确定了 $D_{2} (G)$ 的一个上界，但是这一上界还是可以改进的，我们需要确定图G的一个更加合适的二部划分，进而得到更精确的 $D_{2} (G)$ 的一个上界。具体证明思路及过程需要我们后续进一步的研究。

参考文献

[1]	Turάn, P. (1941) Eine Extremalaufgabe aus der Graphentheorie. Fiz. Lapok, 48, 436-452.
[2]	Erdős, P. and Stone, A.H. (1946) On the Structure of Linear Graphs. Bulletin of the American Mathematical Society, 52, 1089-1091. https://doi.org/10.1090/S0002-9904-1946-08715-7
[3]	Simonovits, M. (1968) A Method for Solving Extremal Problems in Graph Theory, Stability Problems. In: Theory of Graphs (Proc. Colloq. Tihany, 1966), Academic Press, New York, 279-319.
[4]	Brouwer, A.E. (1981) Some Lotto Numbers from an Extension of Turάn’s Theorem. Report ZW152, Math. Centr, Amsterdam, 6 p.
[5]	Alon, N., Balogh, J., Keevash, P. and Sudakov, B. (2004) The Number of Edge Colorings with No Monochrobmatic Cliques. Journal of the London Mathematical Society, 70, 273-288. https://doi.org/10.1112/S0024610704005563
[6]	Amin, K., Faudree, J., Gould, R.J. and Sidorowicz, E. (2013) On the Non-(p-1)-Partite Kp-Free Graphs. Discussiones Mathematicae Graph Theory, 33, 9-23. https://doi.org/10.7151/dmgt.1654
[7]	Balogh, J., Bollobάs, B. and Simonovits, M. (2004) The Number of Graphs without Forbidden Subgraphs. Journal of Combinatorial Theory, Series B, 91, 1-24. https://doi.org/10.1016/j.jctb.2003.08.001
[8]	Hanson, D. and Toft, B. (1991) k-Saturated Graphs of Chromatic Number at Least k. Ars Combinatoria, 31,159-164.
[9]	Kang, M. and Pikhurko, O. (2005) Maximum Kr+1-Free Graphs Which Are Not r-Partite. Matematychni Studii, 24, 12-20.
[10]	Samotij, W. (2014) Stability Results for Random Discrete Structures. Random Structures Random Structures & Algorithms, 44, 269-289. https://doi.org/10.1002/rsa.20477
[11]	Tyomkyn, M. and Uzzel, A.J. (2015) Strong Turάn Stability. The Electronic Journal of Combinatorics, 22, Article No. P3.9. https://doi.org/10.37236/4717
[12]	Wang, J., Wang, S., Yang, W. and Yuan, X. (2011) A Stability Theorem for Maximal C(2k+1)-Free Graphs. arXiv: 2011.11427.
[13]	Fredi, Z. (2015) A Proof of the Stability of Extremal Graphs, Simonovits’ Stability from Szemerdi’s Regublarity. Journal of Combinatorial Theory, Series B, 115, 66-71. https://doi.org/10.1016/j.jctb.2015.05.001
[14]	Roberts, A. and Scott, A. (2018) Stability Results for Graphs with a Critical Edge. European Journal of Combinatorics, 74, 27-38. https://doi.org/10.1016/j.ejc.2018.07.004
[15]	Balogh, J., Clemen, F.C., Lavrov, M., Lidický, B. and Pfender, F. (2019) Making Kr+1-Free Graphs r-Partite. arXiv:1910.00028 preprint.
[16]	Korάndi, D. Roberts, A. and Scott, A. (2021) Exact Stability for Turάn’s Theorem. Advances in Combinatorics. https://doi.org/10.19086/aic.31079
[17]	Fox, J., Himwich, Z. and Mani, N. (2012) Making an H-Free Graph k-Colorbale. arXiv:2102.10220v1.
[18]	Andrάsfai, B., Erdős, P. and Sós, V.T. (1974) On the Connection between Chromatic Number, Maximal Clique and Minimal Degree of a Graph. Discrete Mathematics, 8, 205-218. https://doi.org/10.1016/0012-365X(74)90133-2

为你推荐

友情链接