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