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).
References
[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,http://www.combinatorics.org/, #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
