# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
On embedding well-separable graphs. (English) Zbl 1157.05032
This paper is about guaranteeing that a given graph $H$ is a subgraph of an arbitrary graph $G$. The author considers graphs $H$ that are “far from being an expander”, namely $H$ is well-separable if there is a subset $S \subset V(H)$ of size $o(n)$ such that all components of $H-S$ are of size $o(n)$. Let $\Delta$ denote the maximum degree of $H$ and $\chi$ its chromatic number. The author shows that if $H$ is well-seperable, then for every $\Delta$ and $\gamma > 0$ there exists an $n_0$ such that if $G$ is of order $n \ge n_0$ and minimum degree $\delta(G) \ge (1 - 1/(2(\chi -1)) + \gamma)n$, one gets $H \subset G$. This work can be considered as a generalization of Turán’s Theorem, as well of a generalization of work by Erdös-Stone-Simonovits.
##### MSC:
 05C35 Extremal problems (graph theory) 05C10 Topological graph theory
##### Keywords:
subgraph; well-separable; extremal graph theory
Full Text:
##### References:
 [1] S. Abbasi, Spanning subgraphs of dense graphs, Ph.D. Theses, Department of Computer Science, Rutgers, the State University of New Jersey, 1998. [2] Alon, N.; Yuster, R.: Almost H-factors in dense graphs, Graphs combin. 8, 95-102 (1992) · Zbl 0769.05072 · doi:10.1007/BF02350627 [3] Alon, N.; Yuster, R.: H-factors in dense graphs, J. combin. Theory ser. B 66, 269-282 (1996) · Zbl 0855.05085 · doi:10.1006/jctb.1996.0020 [4] Bollobás, B.: Extremal graph theory, (1978) · Zbl 1099.05044 [5] Csaba, B.: On the bollobás -- eldridge conjecture for bipartite graphs, Comb. probab. Comput. 16, 661-691 (2007) · Zbl 1136.05029 · doi:10.1017/S0963548307008395 [6] Erdős, P.; Simonovits, M.: A limit theorem in graph theory, Studia sci. Math. hungar. 1, 51-57 (1966) · Zbl 0178.27301 [7] Erdős, P.; Stone, A. H.: On the structure of linear graphs, Bull. amer. Math. soc. 52, 1089-1091 (1946) · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7 [8] Hajnal, A.; Szemerédi, E.: Proof of a conjecture of erd\h{o}s, Combinatorial theory and its applications, II, colloquia Mathematica societatis jános bolyai (1970) [9] Komlós, J.: The blow-up lemma (survey), Combin. probab. Comput. 8, 161-176 (1999) · Zbl 0927.05041 · doi:10.1017/S0963548398003502 [10] Komlós, J.; Sárközy, G. N.; Szemerédi, E.: Proof of a packing conjecture of bollobás, Combin. probab. Comput. 4, 241-255 (1995) · Zbl 0842.05072 · doi:10.1017/S0963548300001620 [11] Komlós, J.; Sárközy, G. N.; Szemerédi, E.: Blow-up lemma, Combinatorica 17, 109-123 (1997) · Zbl 0880.05049 [12] Komlós, J.; Sárközy, G. N.; Szemerédi, E.: An algorithmic version of the blow-up lemma, Random struct. Algorithms 12, 297-312 (1998) · Zbl 0917.05071 · doi:10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q [13] Komlós, J.; Sárközy, G. N.; Szemerédi, E.: Proof of the Alon -- yuster conjecture, Discrete math., 255-269 (2001) · Zbl 0977.05106 · doi:10.1016/S0012-365X(00)00279-X [14] Komlós, J.; Sárközy, G. N.; Szemerédi, E.: Spanning trees in dense graphs, Combin. probab. Comput., 397-416 (2001) · Zbl 0998.05012 · doi:10.1017/S0963548301004849 [15] J. Komlós, M. Simonovits, Szemerédi’s Regularity Lemma and its Applications in Graph Theory (survey), Combinatorics Paul Erdős is Eighty, vol. 2, Keszthely, 1993, pp. 295 -- 352. · Zbl 0851.05065 [16] E. Szemerédi, Regular partitions of graphs, Colloques Internationaux C.N.R.S No. 260 --- Problèmes Combinatoires et Théorie des Graphes, Orsay, 1976, pp. 399 -- 401. · Zbl 0413.05055 [17] Turán, P.: On an extremal problem in graph theory, Mat. fiz. Lapok 48, 436-452 (1941)