Journal
COMBINATORICS PROBABILITY & COMPUTING
Volume 18, Issue 3, Pages 455-458Publisher
CAMBRIDGE UNIV PRESS
DOI: 10.1017/S0963548309009687
Keywords
-
Ask authors/readers for more resources
Let r >= 3 and (c/r(r))(r) log n >= 1. If G is a graph of order n and its largest eigenvalue mu(G) satisfies mu(G) >= (1 - 1/(r - 1) + c)n, then G contains a complete r-partite subgraph with r - 1 parts of size [(c/r(r))(r) log n] and one part of size greater than n(1-cr-1). This result implies the Erdos-Stone-Bollobas theorem, the essential quantitative form of the Erdos-Stone theorem. Another easy consequence is that if F-1, F-2,F-... are r-chromatic graphs satisfying v(F-n) = o(log n), then lim(n ->infinity) 1/n max{mu(G) : v(G) = n and F-n not subset of G} = 1 - 1/r - 1.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available