AJCM  Vol.3 No.3 B , September 2013
The Planar Ramsey Numbers PR (K4-e, Kl)

The planar Ramsey number PR (H1, H2) is the smallest integer n such that any planar graph on n vertices contains a copy of H1 or its complement contains a copy of H2. It is known that the Ramsey number R(K4 -e, K6) = 21, and the planar Ramsey numbers PR(K4 - e, Kl) for l ≤ 5 are known. In this paper, we give the lower bounds on PR (K4 ? e, Kl) and determine the exact value of PR (K4 - e, K6).

Cite this paper: Y. Sun, Y. Wu, R. Zhang and Y. Yang, "The Planar Ramsey Numbers PR (K4-e, Kl)," American Journal of Computational Mathematics, Vol. 3 No. 3, 2013, pp. 52-55. doi: 10.4236/ajcm.2013.33B009.

[1]   H. Bielak and I. Gorgol, “On Planar Ramsey Number for a Small and a Complete Graph,” Manuscript, 1997.

[2]   I. Gorgol, “Planar Ramsey Numbers,” Discussiones Mathematicae Graph Theory, Vol. 25, No. 1-2, 2005, pp. 45-50. doi:10.7151/dmgt.1258

[3]   R. Steinberg and C. A. Tovey, “Planar Ramsey Number,” Journal of Combinatorial Theory, Series B, Vol. 59, No. 2, 1993, pp. 288-296. doi:10.1006/jctb.1993.1070

[4]   S. P. Radziszowski, “Small Ramsey Numbers,” Electronic Journal of Combinatorics,, #R13, 2011, p. 84.

[5]   Y. Q. Sun, Y. S. Yang, X. H. Lin and J. Qiao, “The Planar Ramsey Number PR (K4-e, K5),” Discrete Mathematics, Vol. 307, No. 1, 2007, pp. 137-142. doi:10.1016/j.disc.2006.05.034

[6]   Y. Q. Sun, Y. S. Yang and Z. H. Wang, “The Planar Ramsey Number PR (K4-e, Kk-e),” ARS Combinatoria, Vol. 88, 2008, pp. 3-20.

[7]   K. Walker, “The Analog of Ramsey Numbers for Planar Graphs,” Bulletin of the London Mathematical Society, Vol. 1, No. 2, 1969, pp. 187-190. doi:10.1112/blms/1.2.187