Size Ramsey numbers of stars versus cliques

DOI10.1002/JGT.22453MaRDI QIDQ5207469zbMATH OpenOpenAlexWikidataFDO

Authors Meysam Miralaei, G. R. Omidi, M. Shahsiah

Publication date 30 December 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.06599

zbMATH Keywords

Ramsey numberrestricted size Ramsey numbersize Ramsey number

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: The size Ramsey number $hatr(G,H)$ of two graphs $G$ and $H$ is the smallest integer $m$ such that there exists a graph $F$ on $m$ edges with the property that every red-blue colouring of the edges of $F$, yields a red copy of $G$ or a blue copy of $H$. In $1981$, ErdH{o}s observed that $$ and he conjectured that the corresponding upper bound on $hatr(K_{1,k},K_3)$ is sharp. In $1983$, Faudree and Sheehan extended this conjecture as follows: hat{r}(K_{1,k},K_{n})=left { {lr} �inom{k(n-1)+1}{2}-�inom{k}{2} & ~kgeq n~ ext{or}~ k~ ext{odd}. �inom{k(n-1)+1}{2}-k(n-1)/2 & ext{otherwise}. ight. They proved the case $k=2$. In $2001$, Pikhurko showed that this conjecture is not true for $n=3$ and $kgeq5$, disproving the mentioned conjecture of ErdH{o}s. Here we prove Faudree and Sheehan's conjecture for a given $kgeq2$ and $ngeq{k}^3+2k^2+2k$.

Recommendations

• Size Ramsey numbers of stars versus 3-chromatic graphs
• scientific article; zbMATH DE number 16104
• Size ramsey numbers of stars versus 4‐chromatic graphs
• scientific article; zbMATH DE number 1229599
• On a Question of Erdös and Faudree on the Size Ramsey Numbers

Cited in

(9)

• Connected size Ramsey number for matchings vs. small stars or cycles
• On the multicolor size Ramsey number of stars and cliques
• On the restricted size Ramsey number involving a path \(P_3\)
• Size ramsey numbers of stars versus 4‐chromatic graphs
• Size Ramsey numbers of stars versus 3-chromatic graphs
• Rainbow subgraphs in Hamiltonian cycle decompositions of complete graphs
• Size Ramsey numbers of forests versus brooms
• On size multipartite Ramsey numbers involving complete graphs
• Matching-star size Ramsey numbers under connectivity constraint

This page was built for publication: Size Ramsey numbers of stars versus cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207469)