Back to Search Start Over

Ramsey families which exclude a graph

Authors :
Rödl, V.
Sauer, N.
Zhu, X.
Source :
Combinatorica; December 1995, Vol. 15 Issue: 4 p589-596, 8p
Publication Year :
1995

Abstract

For graphsA andB the relationA?(B)<subscript>r</subscript><superscript>1</superscript> means that for everyr-coloring of the vertices ofA there is a monochromatic copy ofB inA. Forb (G) is the family of graphs which do not embedG. A familyFof graphs is Ramsey if for all graphsB?Fthere is a graphA?Fsuch thatA?(B)<subscript>r</subscript><superscript>1</superscript>. The only graphsG for which it is not known whether Forb (G) is Ramsey are graphs which have a cutpoint adjacent to every other vertex except one. In this paper we prove for a large subclass of those graphsG, that Forb (G) does not have the Ramsey property.

Details

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