Closing the gap on path-kipas Ramsey numbers

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

Closing the gap on path-kipas Ramsey numbers

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

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

132 Downloads (Pure)

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 language	Undefined
Pages (from-to)	3.21
Number of pages	8
Journal	The Electronic journal of combinatorics
Volume	22
Issue number	3
Publication status	Published - 14 Aug 2015

Keywords

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

Access to Document

EJCpaper-5007-14723-2-PBFinal published version, 377 KB
EJCpaper-5007-14723-2-PBFinal published version, 377 KB

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p21

Cite this

@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 = aug,

day = "14",

language = "Undefined",

volume = "22",

pages = "3.21",

journal = "The Electronic journal of combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "3",

}

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

SN - 1077-8926

VL - 22

SP - 3.21

JO - The Electronic journal of combinatorics

JF - The Electronic journal of combinatorics

IS - 3

ER -