For two given graphsG1andG2, the planar Ramsey number PR(G1,G2) is the smallest integer N such that for any planar graph G on N vertices, either G containsG1or its complement containsG2. LetCndenote a cycle of length n andKla complete graph of order l. Sun, Yang, Lin and Song conjectured that PR(C4,Kl)=3l + ⌊(l-1)/5⌋-2 and the conjecture was proved for l7. In this paper, it is shown that PR(C4, K8)=23 which confirms the conjecture for l=8.
- Planar graph
- Ramsey number
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics