DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 32(2) (2012) 331-339
DOI: https://doi.org/10.7151/dmgt.1604

On Ramsey (K1, 2, Kn)-minimal Graphs

Mariusz Hałuszczak

Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
Z. Szafrana 4a, Zielona Góra, Poland

Abstract

Let F be a graph and let G, H denote nonempty families of graphs. We write F → (G, H) 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 (G, H)-minimal graph if F → (G, H) and F −e not → (G, H) for every e ∈ E(F).

We present a technique which allows to generate infinite family of (G, H)-minimal graphs if we know some special graphs. In particular, we show how to receive infinite family of (K1, 2, Kn)-minimal graphs, for every n ≥ 3.

Keywords: Ramsey minimal graph, edge coloring, 1-factor, complete graph

2010 Mathematics Subject Classification: 05C55, 05C70, 05C76, 05D10.

References

[1]E.T. Baskoro, L. Yulianti and H. Assiyatun, Ramsey (K1, 2, C4)-minimal graphs, J. Combin. Math. Combin. Comp. 65 (2008) 79--90.
[2]E.T. Baskoro, T. Vetrík and L. Yulianti, Ramsey (K1, 2, C4)-minimal graphs, Discuss. Math. Graph Theory, 30 (2010) 637--649, doi: 10.7151/dmgt.1519.
[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.
[4]M. Borowiecki, I. Schiermeyer and E. Sidorowicz, Ramsey (K1, 2, K3)-minimal graphs, Electron. J. Combin. 12 (2005) #R20.
[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.
[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.
[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.
[10]I. Mengersen, J. Oeckermann, Matching-star Ramsey sets, Discrete Applied Math. 95 (1999) 417--424, doi: 10.1016/S0166-218X(99)00089-X.

Received 13 October 2010
Revised 20 June 2011
Accepted 20 June 2011

Close