Discussiones Mathematicae Graph Theory 30(4) (2010) 637-649
doi: 10.7151/dmgt.1519

[BIBTex] [PDF] [PS]

ON RAMSEY (K1,2, C4)-MINIMAL GRAPHS

Tomás Vetrí k

School of Mathematical Sciences
University of KwaZulu-Natal
Durban, South Africa
e-mail: tomas.vetrik@gmail.com

Lyra Yulianti  and  Edy Tri Baskoro

Combinatorial Mathematics Research Division
Faculty of Mathematics and Natural Sciences
Institut Teknologi Bandung
Bandung, Indonesia
e-mail: lyra@students.itb.ac.id
e-mail: ebaskoro@math.itb.ac.id

Abstract

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 (K1,2,C4)-minimal graphs of any diameter ≥ 4.

Keywords: Ramsey-minimal graph, edge coloring, diameter of a graph.

2010 Mathematics Subject Classification: 05C55, 05D10.

References

[1] E.T. Baskoro, L. Yulianti and H. Assiyatun, Ramsey (K1,2, C4)-minimal graphs, J. Combin. Mathematics and Combin. Computing 65 (2008) 79-90.
[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.
[3] M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey (K1,2, K3)-minimal graphs, Electronic J. Combinatorics 12 (2005) #R20.
[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.
[5] S.A. Burr, P. Erdös and L. Lovász, On graphs of Ramsey type, Ars Combin. 1 (1976) 167-190.
[6] T. Łuczak, On Ramsey-minimal graphs, Electronic J. Combinatorics 1 (1994) #R4.
[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.

Received 3 March 2009
Revised 13 January 2010
Accepted 13 January 2010