关于奇圈稳定性问题的一个注记
A Note on Stability of Odd Cycles
DOI: 10.12677/AAM.2022.112085, PDF,   
作者: 袁小利, 王 健：太原理工大学，数学学院，山西 太原
关键词: Tur?n数；稳定性；奇圈；Tur?n Number； Stability； Odd Cycles
摘要: 令C2k−1是含有2k−1个顶点的图，如果图G不包含图C2k−1作为子图，那么称图G是C2k−1禁止的。本文中，我们证明了对于任意一个n个顶点的图G，如果G是C2k−1禁止的且，那么当n充分大时，图G至多删除260δ2n2条边就可以变为一个二部图。
Abstract: Let C2k−1 be a cycle of length 2k − 1. A graph G is called C2k−1-free if G does not contain C2k−1 as a subgraph. In this paper, we show that if G is a C2k−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] 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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[11] Tyomkyn, M. and Uzzel, A.J. (2015) Strong Turάn Stability. The Electronic Journal of Combinatorics, 22, Article No. P3.9. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[14] Roberts, A. and Scott, A. (2018) Stability Results for Graphs with a Critical Edge. European Journal of Combinatorics, 74, 27-38. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 

为你推荐