RAMSEY NUMBERS FOR CLASS OF EDGELESS, COMPLETE AND STAR GRAPHS

Abstract

For any graph class G of any two positive integers i and j, the Ramsey number RG i; j is the smallest integer such that every graph in G on atleast RG i; j vertices has a clique of size i or an independent set of size j. In this paper, we found the Ramsey numbers for the graph class of edgeless graphs, complete graphs, star graphs and class of all edgeless and complete graphs.

Keywords

• Graph class and Ramsey numbers.

References

1. [1] R.Belmonte, P.Heggernes, P.Van’t Hof and R.Saei, (2012), Ramsey numbers for Line and Perfect Graphs, COCOON 2012 Springer , LNCS 7434: pp.204-215.
2. [2] R.Belmonte, P.Heggernes, P.Van’t Hof and R.Saei, (2014), Graph Class and Ramsey Numbers, Discrete Applied Mathematics, Volume 173, pp.16-27.
3. [3] M.Chundnovsky and P.Seymour, (2005), The Structure of claw-free graphs, Surveys in Combinatorics.
4. [4] Douglas B. West, (1996), Introduction to Graph Theory, Prentice Hall.
5. [5] R.L.Graham, B.L.Rothschild and J.H.Spencer, (1990), Ramsey Theory, Second Edition, Wiley.
6. [6] S.P.Radziszowski, (2014), Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey.
7. [7] F.P.Ramsey, (1930), On a problem of Formal Logic, Proc.London Math.Soc. Series 30, pp.264-286.
8. [8] J.H.Spencer, (1994), Ten Lectures on the Probabilistic Method, SIAM.

9. [9] R.Steinberg and C.A.Tovey, (1993), Planar Ramsey Numbers, J.Comb.Theory Series B, 59, pp.288- 296.
10. [10] K.Walker, (1969), The Analog of Ramsey numbers for Planar Graphs, Bull.London.Math.Sco., 1, pp.187-190.