On edge-disjoint Ramsey numbers of stars

Abstract

For a graph $F$ and a positive integer $t$, the edge-disjoint Ramsey number $E{R}_t(F)$ is the minimum positive integer $n$ such that every red-blue coloring of the edges of the complete graph $K_n$ of order $n$ results in $t$ pairwise edge-disjoint monochromatic copies of a subgraph isomorphic to $F$. Since $E{R}_1(F)$ is in fact the Ramsey number of $F$, this concept extends the standard concept of Ramsey number. We investigate the edge-disjoint Ramsey numbers $E{R}_t(K_{1,n})$ of the stars $K_{1,n}$ of size $n$. Formulas are established for $E{R}_t(K_{1,n})$ for all positive integers $n$ and $t=2,3,4$ and bounds are presented for $E{R}_t(K_{1,n})$ for all positive integers $n$ and $t\ge 5$. Furthermore, exact values of $E{R}_t(K_{1,n})$ are determined for $n=3,4$ and several integers $t\ge 5$.