# On Ramsey $({K}_{1,2},K\u2099)$-minimal graphs

Discussiones Mathematicae Graph Theory (2012)

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

## Access Full Article

top## Abstract

top## How to cite

topMariusz 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] 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] 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] 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] M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey (K_{1, 2}, K₃)-minimal graphs, Electron. J. Combin. 12 (2005) #R20. Zbl1081.05071
- [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] 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] V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93-93.
- [8] R. Diestel, Graph Theory, (2nd ed., Springer - Verlag, New York, 2000).
- [9] T. Łuczak, On Ramsey minimal graphs, Electron. J. Combin. 1 (1994) #R4. Zbl0814.05058
- [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 ?

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