For graphs $G$, $F$ and $H$, let $G\rightarrow (F,H)$ signify that any edge coloring of $G$ in red and blue contains a red $F$ or a blue $H$. The Ramsey number $R(F,H)=\min\{ r|\; K_r\rightarrow (F,H)\}$. In this note, we consider redundant edges in Ramsey graphs, which are associate with critical Ramsey numbers. For an integer $k\ge 1$, let ${ \mathbb G}=\{ G_k,G_{ k+1},\dots \}$ be a class of graphs with $\delta(G_n)\ge 1$. We define the critical Ramsey number $R_{ \mathbb G}(F,H)$ with respect to $\mathbb G$ to be $\max\{ n|\; K_r\setminus G_n \rightarrow(F,H),\,G_n\in{ \mathbb G}\big\}$, where $r=R(F,H)$. We shall determine some $R_{ \mathbb G}(F,H)$, where ${ \mathbb G}$ consists of stars, matchings and complete graphs, respectively.

Categories: math.CO

Redundant edges in Ramsey graphs