Geodesic
The Ramsey Property for Families of Graphs Which Exclude a Given Graph
Canadian journal of mathematics, Tome 44 (1992) no. 5, pp. 1050-1060

Voir la notice de l'article provenant de la source Cambridge University Press

For graphs A, B and a positive integer r, the relation means that whenever Δ is an r-colouring of the vertices of A, then there is an embedding φ of B into A such that Δ ∘ φ is constant. A class of graphs has the Ramsey property if, for every , there is an such that . For a given finite graph G, let Forb(G) denote the class of all finite graphs which do not embed G. It is known that, if G is 2-connected, then Forb() has the Ramsey property, and Forb(G) has the Ramsey property if and only if Forb(G) also has the Ramsey property. In this paper we show that if neither G nor its complement is 2-connected, then either (i) G has a cut point adjacent to every other vertex, or (ii) G has a cut point adjacent to every other vertex except one. We show that Forb(G) has the Ramsey property if G is a path of length 2 or 3, but that Forb(G) does not have the Ramsey property if (i) holds and G is not the path of length 2.
DOI : 10.4153/CJM-1992-064-7
Mots-clés : 05B 
Rödl, V.; Sauer, N. The Ramsey Property for Families of Graphs Which Exclude a Given Graph. Canadian journal of mathematics, Tome 44 (1992) no. 5, pp. 1050-1060. doi: 10.4153/CJM-1992-064-7
@article{10_4153_CJM_1992_064_7,
     author = {R\"odl, V. and Sauer, N.},
     title = {The {Ramsey} {Property} for {Families} of {Graphs} {Which} {Exclude} a {Given} {Graph}},
     journal = {Canadian journal of mathematics},
     pages = {1050--1060},
     year = {1992},
     volume = {44},
     number = {5},
     doi = {10.4153/CJM-1992-064-7},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1992-064-7/}
}
TY  - JOUR
AU  - Rödl, V.
AU  - Sauer, N.
TI  - The Ramsey Property for Families of Graphs Which Exclude a Given Graph
JO  - Canadian journal of mathematics
PY  - 1992
SP  - 1050
EP  - 1060
VL  - 44
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1992-064-7/
DO  - 10.4153/CJM-1992-064-7
ID  - 10_4153_CJM_1992_064_7
ER  - 
%0 Journal Article
%A Rödl, V.
%A Sauer, N.
%T The Ramsey Property for Families of Graphs Which Exclude a Given Graph
%J Canadian journal of mathematics
%D 1992
%P 1050-1060
%V 44
%N 5
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1992-064-7/
%R 10.4153/CJM-1992-064-7
%F 10_4153_CJM_1992_064_7

[1] 1. Erdős, R. and Hajnal, A., On chromatic number of graphs and set systems, Acta. Math. Acad. Sci. Hung. 17(1966), 61–99. Google Scholar

[2] 2. NeSetfil, J. and Rödl, V., Partitions of vertices, Comment. Math. Univ. Carolina 17(1976), 85–95. Google Scholar

[3] 3. Nešetřil, J. and Rödl, V., Partitions of finite relational and set systems, J. Combin. Theory (A) 22, 289–312. Google Scholar

[4] 4. Sauer, N. and Zhu, X., Graphs which do not embed a given graph and the Ramsey property, manuscript. Google Scholar

Cité par Sources :