Non-ramsey graphs are c log n-universal

Authors
Promel, HJ Rodl, V
Citation
Hj. Promel et V. Rodl, Non-ramsey graphs are c log n-universal, J COMB TH A, 88(2), 1999, pp. 379-384
Citations number
6
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
00973165 → ACNP
Volume
88
Issue
2
Year of publication
1999
Pages
379 - 384
Database
ISI
SICI code
0097-3165(199911)88:2<379:NGACLN>2.0.ZU;2-U
Abstract
We prove that for any c(1) >0 there exists c(2)>0 such that the following s tatement is true: If G is a graph with n vertices and with the property tha t neither G nor its complement contains a complete graph K-1, where l=c(1) log n then G is c(2) log n-universal, i.e., G contains all subgraphs with c (2) log n vertices as induced subgraphs. :(C) 1999 Academic Press.