The Planar Ramsey Numbers PR (K4-e, Kl)

DOI: 10.4236/ajcm.2013.33B009   PDF   HTML     2,392 Downloads   3,744 Views   Citations


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).

Share and Cite:

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. 3B, 2013, pp. 52-55. doi: 10.4236/ajcm.2013.33B009.

Conflicts of Interest

The authors declare no conflicts of interest.


[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

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.