Cycles and stability

详细信息    查看全文

• 作者：V. Nikiforov ; R.H. Schelp
• 关键词：Stability ; Turá ; n problems ; Ramsey problems ; Cycles
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2008
• 出版时间：January 2008
• 年：2008
• 卷：98
• 期：1
• 页码：69-84
• 全文大小：168 K

文摘

We prove a number of Turán and Ramsey type stability results for cycles, in particular, the following one: Let NRK4DR-1&_mathId=mml1&_user=10&_cdi=6859&_rdoc=7&_acct=C000050221&_version=1&_userid=10&md5=fadd29ee5b39be6c85d565d3ade83107"" title=""Click to view the MathML source"">n>4, 0<β1/2−1/2n, and the edges of K_(2−β)n be 2-colored so that no monochromatic C_n exists. Then, for some q((1−β)n−1,n), we may drop a vertex v so that in K_(2−β)n−v one of the colors induces 49fe6e5b8"" title=""Click to view the MathML source"">K_{q,(2−β)n−q−1}, while the other one induces K_qK_{(2−β)n−q−1}. We also derive the following Ramsey type result. If n is sufficiently large and G is a graph of order 2n−1, with minimum degree δ(G)(2−10⁻⁶)n, then for every 2-coloring of E(G) one of the colors contains cycles C_t for all t[3,n].