For graphs F, G and H, we write F → (G,H) to mean that any red-blue coloring of the edges of F contains a red copy of G or a blue copy of H. The graph F is Ramsey (G,H)-minimal if F → (G,H) but F* ↛ (G,H) for any proper subgraph F* ⊂ F. We present an infinite family of Ramsey -minimal graphs of any diameter ≥ 4.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1519,
author = {Tom\'as Vetr\'\i k and Lyra Yulianti and Edy Tri Baskoro},
title = {On Ramsey $(K\_{1,2},C4)$-minimal graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {637-649},
zbl = {1217.05163},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1519}
}
Tomás Vetrík; Lyra Yulianti; Edy Tri Baskoro. On Ramsey $(K_{1,2},C₄)$-minimal graphs. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 637-649. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1519/
[000] [1] E.T. Baskoro, L. Yulianti and H. Assiyatun, Ramsey -minimal graphs, J. Combin. Mathematics and Combin. Computing 65 (2008) 79-90. | Zbl 1170.05044
[001] [2] M. Borowiecki, M. Hałuszczak and E. Sidorowicz, On Ramsey-minimal graphs, Discrete Math. 286 (2004) 37-43, doi: 10.1016/j.disc.2003.11.043. | Zbl 1061.05062
[002] [3] M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey -minimal graphs, Electronic J. Combinatorics 12 (2005) R20.
[003] [4] S.A. Burr, P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp, Ramsey-minimal graphs for star-forests, Discrete Math. 33 (1981) 227-237, doi: 10.1016/0012-365X(81)90266-1. | Zbl 0456.05046
[004] [5] S.A. Burr, P. Erdös and L. Lovász, On graphs of Ramsey type, Ars Combin. 1 (1976) 167-190. | Zbl 0333.05120
[005] [6] T. Łuczak, On Ramsey-minimal graphs, Electronic J. Combinatorics 1 (1994) #R4. | Zbl 0814.05058
[006] [7] I. Mengersen and J. Oeckermann, Matching-star Ramsey sets, Discrete Appl. Math. 95 (1999) 417-424, doi: 10.1016/S0166-218X(99)00089-X. | Zbl 0932.05063