Back to Search Start Over

Sparse ramsey graphs

Authors :
Nešetřil, Jaroslav
Rödl, Vojtěch
Source :
Combinatorica; March 1984, Vol. 4 Issue: 1 p71-78, 8p
Publication Year :
1984

Abstract

Abstract: IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer.

Details

Language :
English
ISSN :
02099683 and 14396912
Volume :
4
Issue :
1
Database :
Supplemental Index
Journal :
Combinatorica
Publication Type :
Periodical
Accession number :
ejs14948240
Full Text :
https://doi.org/10.1007/BF02579159