---
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. Journal of Graph Theory.
2024;106(3):663-675. doi:10.1002/jgt.23093
apa: Wigderson, Y. (2024). Ramsey numbers upon vertex deletion. Journal of Graph
Theory. Wiley. https://doi.org/10.1002/jgt.23093
chicago: Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” Journal of
Graph Theory. Wiley, 2024. https://doi.org/10.1002/jgt.23093.
ieee: Y. Wigderson, “Ramsey numbers upon vertex deletion,” Journal of Graph Theory,
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.” Journal of Graph
Theory, vol. 106, no. 3, Wiley, 2024, pp. 663–75, doi:10.1002/jgt.23093.
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'
...
---
OA_place: repository
OA_type: green
_id: '22164'
abstract:
- lang: eng
text: 'The clique removal lemma says that for every ≥r 3 andε > 0, there exists
some δ > 0 so that every n‐vertex graph G with fewer than δnr copies of K r can
be made K r ‐free by removing at most εn2 edges. The dependence of δ on ε in this
result is notoriously difficult to determine: it is known that δ−1 must be at
least super‐polynomial in ε−1, and that it is at most of tower type in εlog −1.
We prove that if one imposes an appropriate minimum degree condition on G, then
one can actually take δ to be a linear function of ε in the clique removal lemma.
Moreover, we determine the threshold for such a minimum degree requirement, showing
that above this threshold we have linear bounds, whereas below the threshold the
bounds are once again super‐polynomial, as in the unrestricted removal lemma.
We also investigate this question for other graphs besides cliques, and prove
some general results about how minimum degree conditions affect the bounds in
the graph removal lemma.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Fox J, Wigderson Y. Minimum degree and the graph removal lemma. Journal
of Graph Theory. 2023;102(4):648-665. doi:10.1002/jgt.22891
apa: Fox, J., & Wigderson, Y. (2023). Minimum degree and the graph removal lemma.
Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22891
chicago: Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal
Lemma.” Journal of Graph Theory. Wiley, 2023. https://doi.org/10.1002/jgt.22891.
ieee: J. Fox and Y. Wigderson, “Minimum degree and the graph removal lemma,” Journal
of Graph Theory, vol. 102, no. 4. Wiley, pp. 648–665, 2023.
ista: Fox J, Wigderson Y. 2023. Minimum degree and the graph removal lemma. Journal
of Graph Theory. 102(4), 648–665.
mla: Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal Lemma.”
Journal of Graph Theory, vol. 102, no. 4, Wiley, 2023, pp. 648–65, doi:10.1002/jgt.22891.
short: J. Fox, Y. Wigderson, Journal of Graph Theory 102 (2023) 648–665.
date_created: 2026-06-29T10:53:26Z
date_published: 2023-04-01T00:00:00Z
date_updated: 2026-07-14T08:24:20Z
day: '01'
doi: 10.1002/jgt.22891
extern: '1'
external_id:
arxiv:
- '2105.09194'
intvolume: ' 102'
issue: '4'
keyword:
- chromatic threshold
- graph removal lemma
- homomorphism threshold
- minimum degree conditions
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2105.09194
month: '04'
oa: 1
oa_version: Preprint
page: 648-665
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: Minimum degree and the graph removal lemma
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 102
year: '2023'
...
---
_id: '9295'
abstract:
- lang: eng
text: "Hill's Conjecture states that the crossing number cr(\U0001D43E\U0001D45B)
\ of the complete graph \U0001D43E\U0001D45B in the plane (equivalently, the
sphere) is 14⌊\U0001D45B2⌋⌊\U0001D45B−12⌋⌊\U0001D45B−22⌋⌊\U0001D45B−32⌋=\U0001D45B4/64+\U0001D442(\U0001D45B3)
. Moon proved that the expected number of crossings in a spherical drawing in
which the points are randomly distributed and joined by geodesics is precisely
\ \U0001D45B4/64+\U0001D442(\U0001D45B3) , thus matching asymptotically the conjectured
value of cr(\U0001D43E\U0001D45B) . Let cr\U0001D443(\U0001D43A) denote the
crossing number of a graph \U0001D43A in the projective plane. Recently, Elkies
proved that the expected number of crossings in a naturally defined random projective
plane drawing of \U0001D43E\U0001D45B is (\U0001D45B4/8\U0001D70B2)+\U0001D442(\U0001D45B3)
. In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked
if lim\U0001D45B→∞ cr\U0001D443(\U0001D43E\U0001D45B)/\U0001D45B4=1/8\U0001D70B2
. We construct drawings of \U0001D43E\U0001D45B in the projective plane that
disprove this."
acknowledgement: "We thank two reviewers for their corrections and suggestions on
the original version of this\r\npaper. This project has received funding from NSERC
Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation
programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg,
Austria."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Dan
full_name: Mcquillan, Dan
last_name: Mcquillan
- first_name: R. Bruce
full_name: Richter, R. Bruce
last_name: Richter
- first_name: Gelasio
full_name: Salazar, Gelasio
last_name: Salazar
- first_name: Matthew
full_name: Sullivan, Matthew
last_name: Sullivan
citation:
ama: Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings
of complete graphs in the projective plane. Journal of Graph Theory. 2021;97(3):426-440.
doi:10.1002/jgt.22665
apa: Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., & Sullivan,
M. (2021). Drawings of complete graphs in the projective plane. Journal of
Graph Theory. Wiley. https://doi.org/10.1002/jgt.22665
chicago: Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar,
and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” Journal
of Graph Theory. Wiley, 2021. https://doi.org/10.1002/jgt.22665.
ieee: A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan,
“Drawings of complete graphs in the projective plane,” Journal of Graph Theory,
vol. 97, no. 3. Wiley, pp. 426–440, 2021.
ista: Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings
of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440.
mla: Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective
Plane.” Journal of Graph Theory, vol. 97, no. 3, Wiley, 2021, pp. 426–40,
doi:10.1002/jgt.22665.
short: A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan,
Journal of Graph Theory 97 (2021) 426–440.
date_created: 2021-03-28T22:01:41Z
date_published: 2021-03-23T00:00:00Z
date_updated: 2025-04-14T07:43:51Z
day: '23'
department:
- _id: UlWa
doi: 10.1002/jgt.22665
ec_funded: 1
external_id:
arxiv:
- '2002.02287'
isi:
- '000631693200001'
intvolume: ' 97'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2002.02287
month: '03'
oa: 1
oa_version: Preprint
page: 426-440
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
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: Drawings of complete graphs in the projective plane
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 97
year: '2021'
...
---
_id: '5790'
abstract:
- lang: eng
text: The partial representation extension problem is a recently introduced generalization
of the recognition problem. A circle graph is an intersection graph of chords
of a circle. We study the partial representation extension problem for circle
graphs, where the input consists of a graph G and a partial representation R′
giving some predrawn chords that represent an induced subgraph of G. The question
is whether one can extend R′ to a representation R of the entire graph G, that
is, whether one can draw the remaining chords into a partially predrawn representation
to obtain a representation of G. Our main result is an O(n3) time algorithm for
partial representation extension of circle graphs, where n is the number of vertices.
To show this, we describe the structure of all representations of a circle graph
using split decomposition. This can be of independent interest.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Steven
full_name: Chaplick, Steven
last_name: Chaplick
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Pavel
full_name: Klavík, Pavel
last_name: Klavík
citation:
ama: Chaplick S, Fulek R, Klavík P. Extending partial representations of circle
graphs. Journal of Graph Theory. 2019;91(4):365-394. doi:10.1002/jgt.22436
apa: Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations
of circle graphs. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22436
chicago: Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial
Representations of Circle Graphs.” Journal of Graph Theory. Wiley, 2019.
https://doi.org/10.1002/jgt.22436.
ieee: S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of
circle graphs,” Journal of Graph Theory, vol. 91, no. 4. Wiley, pp. 365–394,
2019.
ista: Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of
circle graphs. Journal of Graph Theory. 91(4), 365–394.
mla: Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.”
Journal of Graph Theory, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:10.1002/jgt.22436.
short: S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.
date_created: 2018-12-30T22:59:15Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2026-04-16T09:47:19Z
day: '01'
department:
- _id: UlWa
doi: 10.1002/jgt.22436
ec_funded: 1
external_id:
arxiv:
- '1309.2399'
isi:
- '000485392800004'
intvolume: ' 91'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1309.2399
month: '08'
oa: 1
oa_version: Preprint
page: 365-394
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Theory
publication_identifier:
issn:
- 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending partial representations of circle graphs
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 91
year: '2019'
...