Research ArticleOpen AccessGoogle Scholar indexed
The Planar Ramsey Numbers PR (K<sub>4</sub>-e, K<sub>l</sub>)
School of Computer and Information Technology, Beijing jiaotong University, Beijing, China
School of Computer and Information Technology, Beijing jiaotong University, Beijing, China
School of Computer and Information Technology, Beijing jiaotong University, Beijing, China
Department of Computer Science, Dalian University of Technology, Dalian, China
- 1 School of Computer and Information Technology, Beijing jiaotong University, Beijing, China
- 2 School of Computer and Information Technology, Beijing jiaotong University, Beijing, China
- 3 School of Computer and Information Technology, Beijing jiaotong University, Beijing, China
- 4 Department of Computer Science, Dalian University of Technology, Dalian, China
American Journal of Computational Mathematics·Volume 03 (2013)·Pages 52–55·Published 30 September 2013·DOI10.4236/ajcm.2013.33B009
Copy link · social · email
Abstract
The planar Ramsey number PR ( H 1 , H 2 ) is the smallest integer n such that any planar graph on n vertices contains a copy of H 1 or its complement contains a copy of H 2 . It is known that the Ramsey number R ( K 4 - e , K 6 ) = 21, and the planar Ramsey numbers PR ( K 4 - e , K l ) for l ≤ 5 are known. In this paper, we give the lower bounds on PR ( K 4 ? e , K l ) and determine the exact value of PR ( K 4 - e , K 6 ).
KeywordsPlanar GraphRamsey NumberForbidden Subgraph
- H. Bielak and I. Gorgol, “On Planar Ramsey Number for a Small and a Complete Graph,” Manuscript, 1997.
- I. Gorgol, “Planar Ramsey Numbers,” Discussiones Mathematicae Graph Theory, Vol. 25, No. 1-2, 2005, pp. 45-50. doi:10.7151/dmgt.1258
- 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
- S. P. Radziszowski, “Small Ramsey Numbers,” Electronic Journal of Combinatorics,http://www.combinatorics.org/, #R13, 2011, p. 84.
- Y. Q. Sun, Y. S. Yang, X. H. Lin and J. Qiao, “The Planar Ramsey Number PR (K 4 -e, K 5 ),” Discrete Mathematics, Vol. 307, No. 1, 2007, pp. 137-142. doi:10.1016/j.disc.2006.05.034
- Y. Q. Sun, Y. S. Yang and Z. H. Wang, “The Planar Ramsey Number PR (K 4 -e, K k -e),” ARS Combinatoria, Vol. 88, 2008, pp. 3-20.
- 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