The Planar Ramsey Numbers PR (K₄-e, K_l)

Yongqi Sun, Yali Wu, Rui Zhang, Yuansheng Yang

Department of Computer Science, Dalian University of Technology, Dalian, China.
School of Computer and Information Technology, Beijing jiaotong University, Beijing, China.

DOI: 10.4236/ajcm.2013.33B009                

Abstract

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

Keywords

Planar Graph; Ramsey Number; Forbidden Subgraph

Conflicts of Interest

The authors declare no conflicts of interest.

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