On Ramsey ( K 1 , 2 , C ₄ ) -minimal graphs

Tomás Vetrík; Lyra Yulianti; Edy Tri Baskoro

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 4, page 637-649
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Tomás Vetrík, Lyra Yulianti, and Edy Tri Baskoro. "On Ramsey $(K_{1,2},C₄)$-minimal graphs." Discussiones Mathematicae Graph Theory 30.4 (2010): 637-649. <http://eudml.org/doc/270986>.

@article{TomásVetrík2010,
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 $(K_\{1,2\},C₄)$-minimal graphs of any diameter ≥ 4.},
author = {Tomás Vetrík, Lyra Yulianti, Edy Tri Baskoro},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey-minimal graph; edge coloring; diameter of a graph},
language = {eng},
number = {4},
pages = {637-649},
title = {On Ramsey $(K_\{1,2\},C₄)$-minimal graphs},
url = {http://eudml.org/doc/270986},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Tomás Vetrík
AU - Lyra Yulianti
AU - Edy Tri Baskoro
TI - On Ramsey $(K_{1,2},C₄)$-minimal graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 4
SP - 637
EP - 649
AB - 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.
LA - eng
KW - Ramsey-minimal graph; edge coloring; diameter of a graph
UR - http://eudml.org/doc/270986
ER -

References

top
  1. [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. Zbl1170.05044
  2. [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. Zbl1061.05062
  3. [3] M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey ( K 1 , 2 , K ₃ ) -minimal graphs, Electronic J. Combinatorics 12 (2005) R20. 
  4. [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. Zbl0456.05046
  5. [5] S.A. Burr, P. Erdös and L. Lovász, On graphs of Ramsey type, Ars Combin. 1 (1976) 167-190. Zbl0333.05120
  6. [6] T. Łuczak, On Ramsey-minimal graphs, Electronic J. Combinatorics 1 (1994) #R4. Zbl0814.05058
  7. [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. Zbl0932.05063

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.