×

Induced complete \(h\)-partite graphs in dense clique-less graphs. (English) Zbl 0934.05104

Electron. J. Comb. 6, No. 1, Research paper R43, 3 p. (1999); printed version J. Comb. 6, 573-575 (1999).
Let \(h\), \(a\), and \(b\) be fixed positive integers and \(G\) a graph on \(n\) vertices. It is shown that if \(n\) is sufficiently large, \(\delta(G) \geq (hn)/(n-1)\), and \(G\) contains no \(K_b\), then \(G\) contains at least \((1 - o(1))n/(ha)\) vertex-disjoint induced subgraphs that are complete \(h\)-bipartite graphs \(K(h;a)\) with \(a\) vertices in each of the \(h\) parts. The key result used in the proof is the Alon-Yuster result on the existence of vertex-disjoint \(K(h;a)\)’s.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS