TITLE:
The Planar Ramsey Numbers PR (K4-e, Kl)
AUTHORS:
Yongqi Sun, Yali Wu, Rui Zhang, Yuansheng Yang
KEYWORDS:
Planar Graph; Ramsey Number; Forbidden Subgraph
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.3 No.3B,
October
25,
2013
ABSTRACT:
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).