Generalized Ramsey Numbers for Graphs with Three Disjoint Cycles Versus a Complete Graph

Shinya Fujita

Abstract


Let $\mathcal{F},\mathcal{G}$ be families of graphs. The generalized Ramsey number $r(\mathcal{F},\mathcal{G})$ denotes the smallest value of $n$ for which every red-blue coloring of $K_n$ yields a red $F\in\mathcal{F}$ or a blue $G\in \mathcal{G}$. Let $\mathcal{F}(k)$ be a family of graphs with $k$ vertex-disjoint cycles.

In this paper, we deal with the case where $\mathcal{F}=\mathcal{F}(3),\mathcal{G}=\{K_t\}$ for some fixed $t$ with $t\ge 2$, and prove that $r(\mathcal{F}(3),\mathcal{G})=2t+5$.


Keywords


independence number; Ramsey number; vertex-disjoint cycles

Full Text: PDF