[{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Wigderson","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval"}],"article_type":"original","publisher":"Wiley","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2208.11181","open_access":"1"}],"publication_status":"published","_id":"22180","oa_version":"Preprint","quality_controlled":"1","publication":"Journal of Graph Theory","OA_type":"green","external_id":{"unknown":["2208.11181"]},"status":"public","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0364-9024"],"eissn":["1097-0118"]},"day":"01","page":"663-675","volume":106,"date_published":"2024-07-01T00:00:00Z","extern":"1","citation":{"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>.","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>.","ieee":"Y. Wigderson, “Ramsey numbers upon vertex deletion,” <i>Journal of Graph Theory</i>, vol. 106, no. 3. Wiley, pp. 663–675, 2024.","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>","ista":"Wigderson Y. 2024. Ramsey numbers upon vertex deletion. Journal of Graph Theory. 106(3), 663–675.","short":"Y. Wigderson, Journal of Graph Theory 106 (2024) 663–675."},"date_updated":"2026-07-14T09:10:28Z","year":"2024","OA_place":"repository","date_created":"2026-06-29T10:59:24Z","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 ."}],"type":"journal_article","scopus_import":"1","intvolume":"       106","oa":1,"issue":"3","month":"07","title":"Ramsey numbers upon vertex deletion","doi":"10.1002/jgt.23093","article_processing_charge":"No"},{"title":"Minimum degree and the graph removal lemma","doi":"10.1002/jgt.22891","article_processing_charge":"No","arxiv":1,"month":"04","intvolume":"       102","oa":1,"issue":"4","scopus_import":"1","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."}],"type":"journal_article","year":"2023","OA_place":"repository","date_created":"2026-06-29T10:53:26Z","volume":102,"date_published":"2023-04-01T00:00:00Z","extern":"1","date_updated":"2026-07-14T08:24:20Z","citation":{"short":"J. Fox, Y. Wigderson, Journal of Graph Theory 102 (2023) 648–665.","ieee":"J. Fox and Y. Wigderson, “Minimum degree and the graph removal lemma,” <i>Journal of Graph Theory</i>, vol. 102, no. 4. Wiley, pp. 648–665, 2023.","ama":"Fox J, Wigderson Y. Minimum degree and the graph removal lemma. <i>Journal of Graph Theory</i>. 2023;102(4):648-665. doi:<a href=\"https://doi.org/10.1002/jgt.22891\">10.1002/jgt.22891</a>","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.” <i>Journal of Graph Theory</i>, vol. 102, no. 4, Wiley, 2023, pp. 648–65, doi:<a href=\"https://doi.org/10.1002/jgt.22891\">10.1002/jgt.22891</a>.","apa":"Fox, J., &#38; Wigderson, Y. (2023). Minimum degree and the graph removal lemma. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22891\">https://doi.org/10.1002/jgt.22891</a>","chicago":"Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal Lemma.” <i>Journal of Graph Theory</i>. Wiley, 2023. <a href=\"https://doi.org/10.1002/jgt.22891\">https://doi.org/10.1002/jgt.22891</a>."},"publication_identifier":{"issn":["0364-9024"],"eissn":["1097-0118"]},"day":"01","page":"648-665","language":[{"iso":"eng"}],"OA_type":"green","external_id":{"arxiv":["2105.09194"]},"status":"public","quality_controlled":"1","publication":"Journal of Graph Theory","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2105.09194","open_access":"1"}],"_id":"22164","publication_status":"published","oa_version":"Preprint","publisher":"Wiley","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["chromatic threshold","graph removal lemma","homomorphism threshold","minimum degree conditions"],"article_type":"original","author":[{"last_name":"Fox","first_name":"Jacob","full_name":"Fox, Jacob"},{"last_name":"Wigderson","full_name":"Wigderson, Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","first_name":"Yuval"}]},{"status":"public","external_id":{"arxiv":["2002.02287"],"isi":["000631693200001"]},"page":"426-440","day":"23","publication_identifier":{"issn":["0364-9024"],"eissn":["1097-0118"]},"language":[{"iso":"eng"}],"publisher":"Wiley","ec_funded":1,"article_type":"original","author":[{"last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M"},{"last_name":"Mcquillan","first_name":"Dan","full_name":"Mcquillan, Dan"},{"last_name":"Richter","first_name":"R. Bruce","full_name":"Richter, R. Bruce"},{"last_name":"Salazar","first_name":"Gelasio","full_name":"Salazar, Gelasio"},{"full_name":"Sullivan, Matthew","first_name":"Matthew","last_name":"Sullivan"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication":"Journal of Graph Theory","quality_controlled":"1","oa_version":"Preprint","_id":"9295","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2002.02287"}],"month":"03","issue":"3","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.","intvolume":"        97","oa":1,"article_processing_charge":"No","doi":"10.1002/jgt.22665","title":"Drawings of complete graphs in the projective plane","arxiv":1,"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"date_created":"2021-03-28T22:01:41Z","department":[{"_id":"UlWa"}],"year":"2021","citation":{"mla":"Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>, vol. 97, no. 3, Wiley, 2021, pp. 426–40, doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>.","chicago":"Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar, and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>.","apa":"Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., &#38; Sullivan, M. (2021). Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>","short":"A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan, Journal of Graph Theory 97 (2021) 426–440.","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.","ama":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. 2021;97(3):426-440. doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>","ieee":"A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan, “Drawings of complete graphs in the projective plane,” <i>Journal of Graph Theory</i>, vol. 97, no. 3. Wiley, pp. 426–440, 2021."},"date_updated":"2025-04-14T07:43:51Z","date_published":"2021-03-23T00:00:00Z","volume":97,"scopus_import":"1","isi":1,"type":"journal_article","abstract":[{"text":"Hill's Conjecture states that the crossing number  cr(𝐾𝑛)  of the complete graph  𝐾𝑛  in the plane (equivalently, the sphere) is  14⌊𝑛2⌋⌊𝑛−12⌋⌊𝑛−22⌋⌊𝑛−32⌋=𝑛4/64+𝑂(𝑛3) . 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  𝑛4/64+𝑂(𝑛3) , thus matching asymptotically the conjectured value of  cr(𝐾𝑛) . Let  cr𝑃(𝐺)  denote the crossing number of a graph  𝐺  in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of  𝐾𝑛  is  (𝑛4/8𝜋2)+𝑂(𝑛3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if  lim𝑛→∞ cr𝑃(𝐾𝑛)/𝑛4=1/8𝜋2 . We construct drawings of  𝐾𝑛  in the projective plane that disprove this.","lang":"eng"}]},{"publication_identifier":{"issn":["0364-9024"]},"day":"01","page":"365-394","language":[{"iso":"eng"}],"external_id":{"arxiv":["1309.2399"],"isi":["000485392800004"]},"status":"public","quality_controlled":"1","publication":"Journal of Graph Theory","main_file_link":[{"url":"https://arxiv.org/abs/1309.2399","open_access":"1"}],"_id":"5790","oa_version":"Preprint","publication_status":"published","publisher":"Wiley","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","author":[{"last_name":"Chaplick","first_name":"Steven","full_name":"Chaplick, Steven"},{"last_name":"Fulek","first_name":"Radoslav","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klavík, Pavel","first_name":"Pavel","last_name":"Klavík"}],"article_type":"original","ec_funded":1,"title":"Extending partial representations of circle graphs","doi":"10.1002/jgt.22436","article_processing_charge":"No","arxiv":1,"month":"08","intvolume":"        91","oa":1,"issue":"4","isi":1,"scopus_import":"1","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."}],"type":"journal_article","year":"2019","department":[{"_id":"UlWa"}],"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"date_created":"2018-12-30T22:59:15Z","volume":91,"date_published":"2019-08-01T00:00:00Z","date_updated":"2026-04-16T09:47:19Z","citation":{"ieee":"S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of circle graphs,” <i>Journal of Graph Theory</i>, 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.","ama":"Chaplick S, Fulek R, Klavík P. Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. 2019;91(4):365-394. doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>","short":"S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.","apa":"Chaplick, S., Fulek, R., &#38; Klavík, P. (2019). Extending partial representations of circle graphs. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>","chicago":"Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>. Wiley, 2019. <a href=\"https://doi.org/10.1002/jgt.22436\">https://doi.org/10.1002/jgt.22436</a>.","mla":"Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.” <i>Journal of Graph Theory</i>, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:<a href=\"https://doi.org/10.1002/jgt.22436\">10.1002/jgt.22436</a>."}}]