---
OA_place: repository
OA_type: green
_id: '22180'
abstract:
- lang: eng
  text: 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 .
article_processing_charge: No
article_type: original
author:
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Wigderson Y. Ramsey numbers upon vertex deletion. <i>Journal of Graph Theory</i>.
    2024;106(3):663-675. doi:<a href="https://doi.org/10.1002/jgt.23093">10.1002/jgt.23093</a>
  apa: Wigderson, Y. (2024). Ramsey numbers upon vertex deletion. <i>Journal of Graph
    Theory</i>. Wiley. <a href="https://doi.org/10.1002/jgt.23093">https://doi.org/10.1002/jgt.23093</a>
  chicago: Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” <i>Journal of
    Graph Theory</i>. Wiley, 2024. <a href="https://doi.org/10.1002/jgt.23093">https://doi.org/10.1002/jgt.23093</a>.
  ieee: Y. Wigderson, “Ramsey numbers upon vertex deletion,” <i>Journal of Graph Theory</i>,
    vol. 106, no. 3. Wiley, pp. 663–675, 2024.
  ista: Wigderson Y. 2024. Ramsey numbers upon vertex deletion. Journal of Graph Theory.
    106(3), 663–675.
  mla: Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” <i>Journal of Graph
    Theory</i>, vol. 106, no. 3, Wiley, 2024, pp. 663–75, doi:<a href="https://doi.org/10.1002/jgt.23093">10.1002/jgt.23093</a>.
  short: Y. Wigderson, Journal of Graph Theory 106 (2024) 663–675.
date_created: 2026-06-29T10:59:24Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2026-07-14T09:10:28Z
day: '01'
doi: 10.1002/jgt.23093
extern: '1'
external_id:
  unknown:
  - '2208.11181'
intvolume: '       106'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2208.11181
month: '07'
oa: 1
oa_version: Preprint
page: 663-675
publication: Journal of Graph Theory
publication_identifier:
  eissn:
  - 1097-0118
  issn:
  - 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey numbers upon vertex deletion
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 106
year: '2024'
...