A remark on star-C4 and wheel-C4 Ramsey numbers

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

Abstract

Given two graphs G1 and G2, the Ramsey number R(G1;G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).
Original languageUndefined
Pages (from-to)110-114
Number of pages5
JournalElectronic journal of graph theory and applications
Volume2
Issue number2
DOIs
StatePublished - 2014

Fingerprint

Stars
Wheels

Keywords

  • EWI-25792
  • MSC-04C
  • Quadrilateral
  • Ramsey number
  • IR-94683
  • 4-Cycle
  • Wheel
  • METIS-309924
  • Star

Cite this

Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun / A remark on star-C4 and wheel-C4 Ramsey numbers.

In: Electronic journal of graph theory and applications, Vol. 2, No. 2, 2014, p. 110-114.

Research output: Scientific - peer-reviewArticle

@article{87a07522791042a5b7ddebf91f78b03b,
title = "A remark on star-C4 and wheel-C4 Ramsey numbers",
abstract = "Given two graphs G1 and G2, the Ramsey number R(G1;G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).",
keywords = "EWI-25792, MSC-04C, Quadrilateral, Ramsey number, IR-94683, 4-Cycle, Wheel, METIS-309924, Star",
author = "Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
note = "eemcs-eprint-25792 http://eprints.ewi.utwente.nl/25792",
year = "2014",
doi = "10.5614/ejgta.2014.2.2.3",
volume = "2",
pages = "110--114",
journal = "Electronic journal of graph theory and applications",
issn = "2338-2287",
publisher = "Indonesian Combinatorics Society",
number = "2",

}

A remark on star-C4 and wheel-C4 Ramsey numbers. / Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

In: Electronic journal of graph theory and applications, Vol. 2, No. 2, 2014, p. 110-114.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - A remark on star-C4 and wheel-C4 Ramsey numbers

AU - Zhang,Yanbo

AU - Broersma,Haitze J.

AU - Chen,Yaojun

N1 - eemcs-eprint-25792 http://eprints.ewi.utwente.nl/25792

PY - 2014

Y1 - 2014

N2 - Given two graphs G1 and G2, the Ramsey number R(G1;G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).

AB - Given two graphs G1 and G2, the Ramsey number R(G1;G2) is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).

KW - EWI-25792

KW - MSC-04C

KW - Quadrilateral

KW - Ramsey number

KW - IR-94683

KW - 4-Cycle

KW - Wheel

KW - METIS-309924

KW - Star

U2 - 10.5614/ejgta.2014.2.2.3

DO - 10.5614/ejgta.2014.2.2.3

M3 - Article

VL - 2

SP - 110

EP - 114

JO - Electronic journal of graph theory and applications

T2 - Electronic journal of graph theory and applications

JF - Electronic journal of graph theory and applications

SN - 2338-2287

IS - 2

ER -