Ramsey numbers upon vertex deletion
Wigderson Y. 2024. Ramsey numbers upon vertex deletion. Journal of Graph Theory. 106(3), 663–675.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Abstract
Given a graph , its Ramsey number is the minimum so that every two‐coloring of contains a monochromatic copy of . It was conjectured by Conlon, Fox, and Sudakov that if one deletes a single vertex from , the Ramsey number can change by at most a constant factor. We disprove this conjecture, exhibiting an infinite family of graphs such that deleting a single vertex from each decreases the Ramsey number by a super‐constant factor. One consequence of this result is the following. There exists a family of graphs so that in any Ramsey coloring for (i.e., a coloring of a clique on vertices with no monochromatic copy of ), one of the color classes has density .
Publishing Year
Date Published
2024-07-01
Journal Title
Journal of Graph Theory
Publisher
Wiley
Volume
106
Issue
3
Page
663-675
ISSN
eISSN
IST-REx-ID
Cite this
Wigderson Y. Ramsey numbers upon vertex deletion. Journal of Graph Theory. 2024;106(3):663-675. doi:10.1002/jgt.23093
Wigderson, Y. (2024). Ramsey numbers upon vertex deletion. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.23093
Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” Journal of Graph Theory. Wiley, 2024. https://doi.org/10.1002/jgt.23093.
Y. Wigderson, “Ramsey numbers upon vertex deletion,” Journal of Graph Theory, vol. 106, no. 3. Wiley, pp. 663–675, 2024.
Wigderson Y. 2024. Ramsey numbers upon vertex deletion. Journal of Graph Theory. 106(3), 663–675.
Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” Journal of Graph Theory, vol. 106, no. 3, Wiley, 2024, pp. 663–75, doi:10.1002/jgt.23093.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
