Making Kr+1-free graphs r-partite

被引：3

作者：

Balogh, Jozsef ^{[1
,2
]}

Clemen, Felix Christian ^{[1
]}

Lavrov, Mikhail ^{[1
]}

Lidicky, Bernard ^{[3
]}

Pfender, Florian ^{[4
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Moscow Inst Phys & Technol, Moscow, Russia

[3] Iowa State Univ, Dept Math, Ames, IA 50011 USA

[4] Univ Colorado, Dept Math & Stat Sci, Denver, CO 80217 USA

来源：

COMBINATORICS PROBABILITY AND COMPUTING | 2021年 / 30卷 / 04期

关键词：

05C35; 2020 MSC Codes:;

D O I：

10.1017/S0963548320000590

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Erdos-Simonovits stability theorem states that for all epsilon > 0 there exists a > 0 such that if G is a Kr+1-free graph on n vertices with epsilon(G) > ex(n, Kr+1) - alpha n(2), then one can remove epsilon n(2) edges from G to obtain an r-partite graph. Furedi gave a short proof that one can choose alpha = epsilon. We give a bound for the relationship of a and e which is asymptotically sharp as epsilon -> 0.

引用

页码：609 / 618

页数：10

共 18 条

[1] ON THE NON-(p-1)-PARTITE Kp-FREE GRAPHS [J].

Amin, Kinnari ;

Faudree, Jill ;

Gould, Ronald J. ;

Sidorowicz, Elzbieta .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (01) :9-23

[2]

Andrasfai B., 1974, Discrete Mathematics, V8, P205, DOI 10.1016/0012-365X(74)90133-2

[3] THE TYPICAL STRUCTURE OF SPARSE Kr+1-FREE GRAPHS [J].

Balogh, Jozsef ;

Morris, Robert ;

Samotij, Wojciech ;

Warnke, Lutz .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016, 368 (09) :6439-6485

[4]

Brouwer A. E., 1981, Afdeling Zuivere Wiskunde Department of Pure Mathematics, V152

[5]

ERDOS P, 1992, COLLOQ MATH, V60, P239

[6] HOW TO MAKE A GRAPH BIPARTITE [J].

ERDOS, P ;

FAUDREE, R ;

PACH, J ;

SPENCER, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 45 (01) :86-98

[7]

Erdos P., 1970, MAT LAPOK, V21, P249

[8]

ERDOS P, 1966, STUD SCI MATH HUNG, V1, P51

[9] A proof of the stability of extremal graphs, Simonovits' stability from Szemeredi's regularity [J].

Fueredi, Zoltan .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 115 :66-71

[10]

HANSON D, 1991, ARS COMBINATORIA, V31, P159

← 1 2 →