IPM - Institute for Research in Fundamental Sciences

“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 H₁â, â...â, âH_t â, âwe say that G is Ramsey forâ â H₁â, â...â, âH_t and we writeâ â G→ (H₁â, â...â, âH_t) â, âif no matter how one colors the edges ofâ â G with t colorsâ, âsay 1,...â, ât â, âthere exists a monochromatic copy of H_i in the i th colorâ â for some 1 ≤ i ≤ t â. âThe multicolor Ramsey numberâ â r(H₁â, â...â, âH_t) is the smallest integer n such that the complete graphâ â K_n is Ramsey for (H₁â, â...â, âH_t) â. â The multicolor size Ramsey numberâ â ∧r(H₁â, â...â, âH_t) is defined asâ â min{ |E(G)|â: âG→ (H₁â, â...â, âH_t) } â, âwhile the restricted size Ramsey numberâ â ∧r^*(H₁â, â...â, âH_t) is defined asâ â

ââ

(H₁â, â...â, âH_t)=

min

{ |E(G)|â: âG→ (H₁â, â...â, âH_t)â â and â â|V(G)|=r(H₁â, â...â, âH_t) }â.â

â â â 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(K_{1,q₁â, â...â, âK_{1,q_n}}) and r(K_p₁â, â...â, âK_{p_m}) â. â 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

“School of Mathematics”

People

Schools

Centers

Groups

E-Services

Publications