paper

On the set-coloring Ramsey numbers of graphs

arXiv:2505.20652

Abstract

The \textit{set-coloring Ramsey number} $R_{r, s} (G_{1}, G_{2}, ..., G_{r})$ is the least $n \in N$ such that every coloring $I ¨ : E (K_{n}) \to (s [ r ])$ contains a monochromatic copy of $G_{i}$ , that is, a color $i \in [r]$ such that $i \in I ¨ (e)$ for every $e \in E (G_{i})$ . If $G_{1} = G_{2} = \dots = G_{r} = G$ , then we write $R_{r, s} (G)$ for short. In 2022, Le asked to find lower and upper bounds for $R_{s, t} (G)$ with various kinds of graphs $G$ such as stars, paths, cycles, etc. In this paper, we obtain exact values or bounds for the set-coloring Ramsey numbers of stars, paths, matchings, etc. By LovÃ¡sz Local Lemma, we give a lower bound for the set-coloring Ramsey number for general graphs.