Size Ramsey minimal graphs for star forests
read the original abstract
For given graphs $G_{1}, G_{2}, \dots, G_{t}$ and $G$, let $G\rightarrow (G_{1}, G_{2}, \dots, G_{t})$ denote that each $t$-coloring of $E(G)$ yields a monochromatic copy of $G_{i}$ in color $i$ for some $i\in [t]$. The {\it size Ramsey number} $\hat{r}(G_{1}, G_{2}, \dots, G_{t})$ is the minimum size of $G$ such that $G\rightarrow (G_{1}, G_{2}, \dots, G_{t})$. A graph $G$ is a {\it size Ramsey minimal graph} for $(G_{1}, G_{2}, \dots, G_{t})$ if $G\rightarrow (G_{1}, G_{2}, \dots, G_{t})$ and $e(G)= \hat{r}(G_{1}, G_{2}, \dots, G_{t})$. A {\it star forest} is a vertex-disjoint union of stars, and a {\it uniform star forest} is a star forest with the same size of each component. In 1978, Burr, Erd\H{o}s, Faudree, Rousseau and Schelp, and in 2025, Davoodi, Javadi, Kamranian and Raeisi completely characterized the size minimal graphs for uniform star forests. In this paper, we completely characterize the size Ramsey minimal graphs for uniform star forests in multicolors.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.