Closing the Gap on Path-Kipas Ramsey Numbers

  • Binlong Li
  • Yanbo Zhang
  • Halina Bielak
  • Hajo Broersma
  • Premek Holub
Keywords: Ramsey number, path, kipas

Abstract

Given two graphs $G_1$ and $G_2$, the Ramsey number $R(G_1, G_2)$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G_1$ is a subgraph of $G$, or $G_2$ is a subgraph of the complement of $G$. Let $P_n$ denote a path of order $n$ and $\widehat{K}_m$ a kipas of order $m+1$, i.e., the graph obtained from a $P_m$ by adding one new vertex $v$ and edges from $v$ to all vertices of the $P_m$.

We close the gap in existing knowledge on exact values of the Ramsey numbers $R(P_n,\widehat{K}_m)$ by determining the exact values for the remaining open cases.
Published
2015-08-14
Article Number
P3.21