The planar Ramsey number PR(C4, K8)

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

doi:10.1016/j.dam.2014.02.002

The planar Ramsey number PR(C₄, K₈)

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

Research output: Journal article publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	28-34
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	171
DOIs	https://doi.org/10.1016/j.dam.2014.02.002
Publication status	Published - 10 Jul 2014

Keywords

Clique
Planar graph
Quadrilateral
Ramsey number

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

More information

10.1016/j.dam.2014.02.002

Cite this

@article{84223e5b6e8d4cddb28853baf8f24f0b,

title = "The planar Ramsey number PR(C4, K8)",

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.",

keywords = "Clique, Planar graph, Quadrilateral, Ramsey number",

author = "Yaojun Chen and Cheng, {Edwin Tai Chiu} and Yunqing Zhang and Guofei Zhou",

year = "2014",

month = jul,

day = "10",

doi = "10.1016/j.dam.2014.02.002",

language = "English",

volume = "171",

pages = "28--34",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - The planar Ramsey number PR(C4, K8)

AU - Chen, Yaojun

AU - Cheng, Edwin Tai Chiu

AU - Zhang, Yunqing

AU - Zhou, Guofei

PY - 2014/7/10

Y1 - 2014/7/10

N2 - 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.

AB - 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.

KW - Clique

KW - Planar graph

KW - Quadrilateral

KW - Ramsey number

UR - http://www.scopus.com/inward/record.url?scp=84898548758&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2014.02.002

DO - 10.1016/j.dam.2014.02.002

M3 - Journal article

SN - 0166-218X

VL - 171

SP - 28

EP - 34

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -