Metadata only
Date
2020Type
- Journal Article
Abstract
Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red-blue coloring of the edges of the complete graph K-N contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) >= (vertical bar G vertical bar - 1) (chi(H) - 1) + sigma(H), where chi(H) is the chromatic number of H and sigma(H) is the size of the smallest color class in a chi(H)-coloring of H. A graph G is called H-good if R(G, H) = (vertical bar G vertical bar - 1) (chi(H) - 1) + sigma(H). The notion of Ramsey goodness was introduced by Burr and Erdos in 1983 and has been extensively studied since then. In this paper we show that if n >= 10(60)vertical bar H vertical bar and sigma(H) >= chi(H)(22), then the n-vertex cycle C-n is H-good. For graphs H with high chi(H) and sigma(H), this proves in a strong form a conjecture of Allen, Brightwell, and Skokan. © 2020 Society for Industrial and Applied Mathematics. Show more
Publication status
publishedExternal links
Journal / series
SIAM Journal on Discrete MathematicsVolume
Pages / Article No.
Publisher
SIAMSubject
Ramsey theory; Cycles; ExpandersOrganisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Funding
175573 - Extremal problems in combinatorics (SNF)
More
Show all metadata