The planar Ramsey number PR(C4, K8)

Yaojun Chen, Edwin Tai Chiu Cheng, Yunqing Zhang, Guofei Zhou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)28-34
Number of pages7
JournalDiscrete Applied Mathematics
Volume171
DOIs
Publication statusPublished - 10 Jul 2014

Keywords

  • Clique
  • Planar graph
  • Quadrilateral
  • Ramsey number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this