On Ramsey $(K_{1,2},C₄)$-minimal graphs

• Autorzy: Tomás Vetrík , Lyra Yulianti , Edy Tri Baskoro
• Języki publikacji: EN

Abstrakty

EN

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 $(K_{1,2},C₄)$-minimal graphs of any diameter ≥ 4.

Słowa kluczowe

EN

Ramsey-minimal graph; edge coloring; diameter of a graph

Kategorie tematyczne

• 05D10: Ramsey theory
• 05C55: Generalized Ramsey theory

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 4
• Strony: 637-649

Daty

wydano

2010

otrzymano

2009-03-03

poprawiono

2010-01-13

zaakceptowano

2010-01-13

Twórcy

autor

Tomás Vetrík

• School of Mathematical Sciences, University of KwaZulu-Natal, Durban, South Africa

autor

Lyra Yulianti

• Combinatorial Mathematics Research Division, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

autor

Edy Tri Baskoro

• Combinatorial Mathematics Research Division, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

Bibliografia

• [1] E.T. Baskoro, L. Yulianti and H. Assiyatun, Ramsey $(K_{1,2},C₄)$-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 $(K_{1,2},K₃)$-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.

Identyfikatory

DOI

10.7151/dmgt.1519