---
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. <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>
  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>.
  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.
  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>.
  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'
...