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

Mariusz Hałuszczak

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 2, page 331-339
  • ISSN: 2083-5892

Abstract

top
Let F be a graph and let , denote nonempty families of graphs. We write F → (,) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (,)-minimal graph if F → (,) and F - e not → (,) for every e ∈ E(F). We present a technique which allows to generate infinite family of (,)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of ( K 1 , 2 , K ) -minimal graphs, for every n ≥ 3.

How to cite

top

Mariusz Hałuszczak. "On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs." Discussiones Mathematicae Graph Theory 32.2 (2012): 331-339. <http://eudml.org/doc/270989>.

@article{MariuszHałuszczak2012,
abstract = {Let F be a graph and let , denote nonempty families of graphs. We write F → (,) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (,)-minimal graph if F → (,) and F - e not → (,) for every e ∈ E(F). We present a technique which allows to generate infinite family of (,)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of $(K_\{1,2\}, Kₙ)$-minimal graphs, for every n ≥ 3.},
author = {Mariusz Hałuszczak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey minimal graph; edge coloring; 1-factor; complete graph},
language = {eng},
number = {2},
pages = {331-339},
title = {On Ramsey $(K_\{1,2\}, Kₙ)$-minimal graphs},
url = {http://eudml.org/doc/270989},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Mariusz Hałuszczak
TI - On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 2
SP - 331
EP - 339
AB - Let F be a graph and let , denote nonempty families of graphs. We write F → (,) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (,)-minimal graph if F → (,) and F - e not → (,) for every e ∈ E(F). We present a technique which allows to generate infinite family of (,)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of $(K_{1,2}, Kₙ)$-minimal graphs, for every n ≥ 3.
LA - eng
KW - Ramsey minimal graph; edge coloring; 1-factor; complete graph
UR - http://eudml.org/doc/270989
ER -

References

top
  1. [1] E.T. Baskoro, L. Yulianti and H. Assiyatun, Ramsey (K_{1, 2}, C₄)-minimal graphs, J. Combin. Math. Combin. Comp. 65 (2008) 79-90. Zbl1170.05044
  2. [2] E.T. Baskoro, T. Vetrík and L. Yulianti, Ramsey (K_{1, 2}, C₄)-minimal graphs, Discuss. Math. Graph Theory, 30 (2010) 637-649, doi: 10.7151/dmgt.1519. Zbl1217.05163
  3. [3] 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
  4. [4] M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey (K_{1, 2}, K₃)-minimal graphs, Electron. J. Combin. 12 (2005) #R20. Zbl1081.05071
  5. [5] S.A. Burr, P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp, Ramsey-minimal graphs for the pair star, connected graph, Studia Sci. Math. Hungar. 15 (1980) 265-273. Zbl0438.05046
  6. [6] 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
  7. [7] V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93-93. 
  8. [8] R. Diestel, Graph Theory, (2nd ed., Springer - Verlag, New York, 2000). 
  9. [9] T. Łuczak, On Ramsey minimal graphs, Electron. J. Combin. 1 (1994) #R4. Zbl0814.05058
  10. [10] I. Mengersen, J. Oeckermann, Matching-star Ramsey sets, Discrete Applied 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.