A Note on the Multicolor Size-Ramsey Numbers of Connected Graphs
The Electronic Journal of Combinatorics · 19.06.2026 · 33 (2)
DOI: 10.37236/12948 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 19.06.2026. Verfasst von Louis DeBiasio.
Abstract (Originalsprache)
The $r$-color size-Ramsey number of a graph $H$, denoted by $\widehat{R}_r(H)$, is the minimum number of edges in a graph $G$ having the property that every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H$. Krivelevich (2019) proved that $\widehat{R}_r(P_{m+1})=\Omega(r^2m)$ where $P_{m+1}$ is the path on $m$ edges. He explains that his proof actually applies to any connected graph $H$ with $m$ edges and vertex cover number larger than $\sqrt{m}$. He also notes that some restriction on the vertex cover number is necessary since the star with $m$ edges, $K_{1,m}$, has vertex cover number 1 and satisfies $\widehat{R}_r(K_{1,m})=r(m-1)+1$. We prove that the star is actually the only exception; that is, $\widehat{R}_r(H)=\Omega(r^2m)$ for every non-star connected graph $H$ with $m$ edges. We also prove a strengthening of this result for trees. It follows from results of Beck (1990) and Dellamonica (2012) that $\widehat{R}_2(T)=\Theta(\beta(T))$ for every tree $T$ with bipartition $\{V_1, V_2\}$ and $\beta(T)=|V_1|\max\{d(v):v\in V_1\}+|V_2|\max\{d(v):v\in V_2\}$. We prove that $\widehat{R}_r(T)=\Omega(r^2\beta(T))$ for every tree $T$, again with the exception of the star. Additionally, we prove that for the family of non-star trees $T$ with $\beta(T)=\Omega(n_1n_2)$ (which includes all non-star trees of linear maximum degree and all trees of radius 2 for example) we have $\widehat{R}_r(T)=\Theta(r^2\beta(T))$.
Zitieren
APA
DeBiasio, L. (2026). A Note on the Multicolor Size-Ramsey Numbers of Connected Graphs. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/12948
Vancouver
DeBiasio L. A Note on the Multicolor Size-Ramsey Numbers of Connected Graphs. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/12948
BibTeX
@article{DeBiasio2026,
author = {DeBiasio, Louis},
title = {A Note on the Multicolor Size-Ramsey Numbers of Connected Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/12948}
}
EUVIMED