Sparse ramsey graphs |
| |
| Authors: | Jaroslav Ne?et?il Vojtěch Rödl |
| |
| Institution: | (1) Department of Cybernetics, Charles University, Malostranské nám. 25, Praha 1, Czechoslovakia;(2) FJFI ČVUT Department of Mathematics, Husova 5, Praha 1, Czechoslovakia |
| |
| 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.
Dedicated to Paul Erdős on his seventieth birthday |
| |
| Keywords: | 05 C 55 05 C 38 05 C 65 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
