Closing the Gap on Path-Kipas Ramsey Numbers

Binlong Li, Yanbo Zhang, Halina Bielak, Hajo Broersma, Premek Holub

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.

Keywords


Ramsey number; path; kipas

Full Text: PDF