On the star-critical Ramsey number of a forest versus complete graphs

Azam Kamranian; Ghaffar Raeisi

paper

On the star-critical Ramsey number of a forest versus complete graphs

arXiv:1912.00703

Abstract

Let $G$ and $G_{1}, G_{2}, \dots, G_{t}$ be given graphs. By $G \to (G_{1}, G_{2}, \dots, G_{t})$ we mean if the edges of $G$ are arbitrarily colored by $t$ colors, then for some $i$ , $1 \leq i \leq t$ , the spanning subgraph of $G$ whose edges are colored with the $i$ -th color, contains a copy of $G_{i}$ . The Ramsey number $R (G_{1}, G_{2}, \dots, G_{t})$ is the smallest positive integer $n$ such that $K_{n} \to (G_{1}, G_{2}, \dots, G_{t})$ and the size Ramsey number $R^(G_{1}, G_{2}, \dots, G_{t})$ is defined as $min {∣ E (G) ∣ : G \to (G_{1}, G_{2}, \dots, G_{t})}$ . Also, for given graphs $G_{1}, G_{2}, \dots, G_{t}$ with $r = R (G_{1}, G_{2}, \dots, G_{t})$ , the star-critical Ramsey number $R_{*} (G_{1}, G_{2}, \dots, G_{t})$ is defined as $min {δ (G) : G \subseteq K_{r}, G \to (G_{1}, G_{2}, \dots, G_{t})}$ . In this paper, the Ramsey number and also the star-critical Ramsey number of a forest versus any number of complete graphs will be computed exactly in terms of the Ramsey number of complete graphs. As a result, the computed star-critical Ramsey number is used to give a tight bound for the size Ramsey number of a forest versus a complete graph.

11 pages, 1 figure