“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16310
School of Mathematics
  Title:   On the multicolor size Ramsey number of stars and cliques
  Author(s):  Maryam Shahsiah (Joint with M. Miralaei)
  Status:   Published
  Journal: Discrete Math.
  Vol.:  343
  Year:  2020
  Pages:   111899
  Supported by:  IPM
  Abstract:
For given graphs H1‎, ‎...‎, ‎Ht ‎, ‎we say that G is Ramsey for‎ ‎ H1‎, ‎...‎, ‎Ht and we write‎ ‎ G→ (H1‎, ‎...‎, ‎Ht) ‎, ‎if no matter how one colors the edges of‎ ‎ G with t colors‎, ‎say 1,...‎, ‎t ‎, ‎there exists a monochromatic copy of Hi in the i th color‎ ‎ for some 1 ≤ it ‎. ‎The multicolor Ramsey number‎ ‎ r(H1‎, ‎...‎, ‎Ht) is the smallest integer n such that the complete graph‎ ‎ Kn is Ramsey for (H1‎, ‎...‎, ‎Ht) ‎. ‎ The multicolor size Ramsey number‎ ‎ r(H1‎, ‎...‎, ‎Ht) is defined as‎ ‎ min{ |E(G)|‎: ‎G→ (H1‎, ‎...‎, ‎Ht) } ‎, ‎while the restricted size Ramsey number‎ ‎ r*(H1‎, ‎...‎, ‎Ht) is defined as‎ ‎
‎‎
^
r
 
*
 
(H1‎, ‎...‎, ‎Ht)= min
{ |E(G)|‎: ‎G→ (H1‎, ‎...‎, ‎Ht)‎ ‎ and â€Ž ‎|V(G)|=r(H1‎, ‎...‎, ‎Ht) }‎.‎
‎ ‎ ‎ In 1978 Erdös et al‎. ‎initiated the study of the size Ramsey numbers of‎ ‎ graphs‎. ‎Afterwards‎, ‎size Ramsey numbers‎ ‎ have been studied with particular focus on the case of trees‎, ‎sparse graphs and bounded degree graphs‎. ‎ In this paper‎, ‎the order of magnitude of‎ ‎ multicolor size Ramsey number of stars and cliques is determined in terms of r(K1,q1‎, ‎...‎, ‎K1,qn) and r(Kp1‎, ‎...‎, ‎Kpm) ‎. ‎ Moreover‎, ‎in some special cases‎, ‎ restricted size Ramsey number of stars and cliques is determined exactly‎. ‎Our results have‎, ‎up to a constant factor‎, ‎similar order of magnitude and‎ ‎ generalize significantly a well known result of Faudree and Sheehan.
‎

Download TeX format
back to top
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right