Blow-up Lemma

J�nos Koml�s; G�bor N. S�rk�zy; Endre Szemer�di

doi:10.1007/bf01196135

journal article Mar 01, 1997

Blow-up Lemma

J�nos Koml�s G�bor N. S�rk�zy Endre Szemer�di

Combinatorica Vol. 17 No. 1 pp. 109-123 · Springer Science and Business Media LLC

View at Publisher Save 10.1007/bf01196135

Topics

No keywords indexed for this article. Browse by subject →

References

16

[1]

N. Alon, R. Duke, H. Leffman, V. R�dl, andR. Yuster: Algorithmic aspects of the regularity lemma.FOCS,33 (1993), 479?481; Journal of Algorithms,16 (1994), 80?109.

[2]

N. Alon andE. Fischer: 2-factors in dense graphs, Discrete Math., to appear.

[3]

N. Alon, S. Friedland, G. Kalai: Regular subgraphs of almost regular graphs,J. Combinatorial Theory, B37 (1984), 79?91. See alsoN. Alon, S. Friedland, G. Kalai: Every 4-regular graph plus an edge contains a 3-regular subgraph,J. Combinatorial Theory, B37 (1984), 91?92. 10.1016/0095-8956(84)90047-9

[4]

N. Alon andR. Yyster: AlmostH-factors in dense graphs,Graphs and Combinatorics,8 (1992), 95?102. 10.1007/bf02350627

[5]

N. Alon andR. Yuster:H-factors in dense graphs,J. Combinatorial Theory, Ser. B, to appear.

[6]

V. Ghv�tal, V. R�dl, E. Szemer�di, andW. T. Trotter Jr.: The Ramsey number of a graph with bounded maximum degree,Journal of Combinatorial Theory, B34 (1983), 239?243. 10.1016/0095-8956(83)90037-0

[7]

K. Corr�di andA. Hajnal: On the maximal number of independent circuits in a graph,Acta Math. Acad. Sci. Hung.,14 (1963), 423?439. 10.1007/bf01895727

[8]

T. K?v�ri, Vera T. S�s, andP. Tur�n: On a problem of Zarankiewicz,Colloq. Math.,3 (1954), 50?57. 10.4064/cm-3-1-50-57

[9]

P. Erd?s andA. H. Stone: On the structure of linear graphs,Bull. Amer. Math. Soc.,52 (1946), 1089?1091.

[10]

A. Hajnal andE. Szemer�di: Proof of a conjecture of Erd?s,Combinatorial Theory and its Applications vol. II (P. Erd?s, A. R�nyi and V. T. S�s (eds.), Colloq. Math. Soc. J. Bolyai 4, North-Holland, Amsterdam (1970), 601?623.

[11]

J. Koml�s, G. N. S�rk�zy, andE. Szemer�di: Proof of a packing conjecture of Bollob�s, AMS Conference on Discrete Mathematics, DeKalb, Illinois (1993),Combinatorics, Probability and Computing,4 (1995), 241?255. 10.1017/s0963548300001620

[12]

J. Koml�s, G. N. S�rk�zy, andE. Szemer�di: On the P�sa-Seymour conjecture, submitted to theJournal of Graph Theory.

[13]

J. Koml�s, G. N. S�rk�zy, andE. Szemer�di: On the square of a Hamiltonian cycle in dense graphs, Proceedings of Atlanta'95,Random Structures and Algorithms,9 (1996), 193?211. 10.1002/(sici)1098-2418(199608/09)9:1/2<193::aid-rsa12>3.0.co;2-p

[14]

J. Koml�s, G. N. S�rk�zy, andE. Szemer�di: Proof of the Alon-Yuster conjecture, in preparation.

[15]

J. Koml�s andM. Simonovits: Szemer�di's Regularity Lemma and its applications in graph theory, Bolyai Society Mathematical Studies 2,Combinatorics, Paul Erd?s is Eighty (Volume 2), (D. Mikl�s, V. T. S�s, T. Sz?nyi eds.), Keszthely (Hungary) (1993), Budapest (1996), 295?352.

[16]

E. Szemer�di: Regular partitions of graphs, Colloques Internationaux C.N.R.S. N o 260 ?Probl�mes Combinatoires et Th�orie des Graphes, Orsay (1976), 399?401.

Cited By

180

Approximate multipartite version of the Hajnal–Szemerédi theorem

Béla Csaba, Marcelo Mydlarz · 2012

Journal of Combinatorial Theory, Se...

A hypergraph blow‐up lemma

Peter Keevash · 2011

Random Structures & Algorithms

The minimum degree threshold for perfect graph packings

DANIELA KÜHN, DERYK OSTHUS · 2009

Combinatorica

Quadripartite version of the Hajnal–Szemerédi theorem