Closing the gap on path-kipas Ramsey numbers

Binlong Li, Yanbo Zhang, Halina Bielak, Haitze J. Broersma, Premysl Holub

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 Pn denote a path of order n and K^m a kipas of order m + 1, i.e., the graph obtained from a Pm by adding one new vertex v and edges from v to all vertices of the Pm. We close the gap in existing knowledge on exact values of the Ramsey numbers R(Pn,K^m) by determining the exact values for the remaining open cases.
Original languageUndefined
Pages (from-to)3.21
Number of pages8
JournalElectronic journal of combinatorics
Volume22
Issue number3
StatePublished - 14 Aug 2015

Keywords

  • MSC-05C
  • EWI-26317
  • Ramsey number
  • IR-98275
  • Path
  • METIS-314968
  • Kipas

Cite this

Li, B., Zhang, Y., Bielak, H., Broersma, H. J., & Holub, P. (2015). Closing the gap on path-kipas Ramsey numbers. Electronic journal of combinatorics, 22(3), 3.21.

Li, Binlong; Zhang, Yanbo; Bielak, Halina; Broersma, Haitze J.; Holub, Premysl / Closing the gap on path-kipas Ramsey numbers.

In: Electronic journal of combinatorics, Vol. 22, No. 3, 14.08.2015, p. 3.21.

Research output: Scientific - peer-reviewArticle

@article{fac387faf6ae456ba2f8aa31d6874e86,
title = "Closing the gap on path-kipas 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 Pn denote a path of order n and K^m a kipas of order m + 1, i.e., the graph obtained from a Pm by adding one new vertex v and edges from v to all vertices of the Pm. We close the gap in existing knowledge on exact values of the Ramsey numbers R(Pn,K^m) by determining the exact values for the remaining open cases.",
keywords = "MSC-05C, EWI-26317, Ramsey number, IR-98275, Path, METIS-314968, Kipas",
author = "Binlong Li and Yanbo Zhang and Halina Bielak and Broersma, {Haitze J.} and Premysl Holub",
note = "eemcs-eprint-26317",
year = "2015",
month = "8",
volume = "22",
pages = "3.21",
journal = "Electronic journal of combinatorics",
issn = "1077-8926",
publisher = "Electronic Journal of Combinatorics",
number = "3",

}

Li, B, Zhang, Y, Bielak, H, Broersma, HJ & Holub, P 2015, 'Closing the gap on path-kipas Ramsey numbers' Electronic journal of combinatorics, vol 22, no. 3, pp. 3.21.

Closing the gap on path-kipas Ramsey numbers. / Li, Binlong; Zhang, Yanbo; Bielak, Halina; Broersma, Haitze J.; Holub, Premysl.

In: Electronic journal of combinatorics, Vol. 22, No. 3, 14.08.2015, p. 3.21.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Closing the gap on path-kipas Ramsey numbers

AU - Li,Binlong

AU - Zhang,Yanbo

AU - Bielak,Halina

AU - Broersma,Haitze J.

AU - Holub,Premysl

N1 - eemcs-eprint-26317

PY - 2015/8/14

Y1 - 2015/8/14

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 Pn denote a path of order n and K^m a kipas of order m + 1, i.e., the graph obtained from a Pm by adding one new vertex v and edges from v to all vertices of the Pm. We close the gap in existing knowledge on exact values of the Ramsey numbers R(Pn,K^m) by determining the exact values for the remaining open cases.

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 Pn denote a path of order n and K^m a kipas of order m + 1, i.e., the graph obtained from a Pm by adding one new vertex v and edges from v to all vertices of the Pm. We close the gap in existing knowledge on exact values of the Ramsey numbers R(Pn,K^m) by determining the exact values for the remaining open cases.

KW - MSC-05C

KW - EWI-26317

KW - Ramsey number

KW - IR-98275

KW - Path

KW - METIS-314968

KW - Kipas

M3 - Article

VL - 22

SP - 3.21

JO - Electronic journal of combinatorics

T2 - Electronic journal of combinatorics

JF - Electronic journal of combinatorics

SN - 1077-8926

IS - 3

ER -