Skip to content
DraconiticResearch
Search Sources API
190,332 studies31 sourcesUpdated 25 min ago
PreprintCC BY 4.0arXiv

Finite deletion-induced saturation for every non-complete graph

  • Haochen Liu
Open at sourcePDFDOICite

Abstract

A graph G is deletion-induced-saturated for H if G has an edge, contains no induced copy of H, and deleting any edge of G creates an induced copy of H. We prove, with finite certificate verification, that a finite graph H admits such a finite graph G if and only if H is not complete. This resolves the deletion conjecture of Fan, Hajebi, Hajebi and Spirkl. The main step transfers suitable free amalgamations to finite extensions using a local lifting theorem of Auinger, Bitterlich and Otto. A second criterion treats edge addition by protecting specified nonedges and then taking a maximal induced-H-free completion. Structural results of Bonamy, Groenland, Johnston, Morrison and Scott reduce the remaining targets to dense templates and a finite hereditary class. Two uniform constructions in halved cubes handle the dense templates. The finite part is supported by exhaustive coverage certificates, structural certificates and explicit hosts, including a circulant graph on $30$ vertices.

Related

  1. When Listwise Deletion Works: Causal Diagrams and Complete-Case Regression
    Wenxin Lin, Shiyao Liu
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. Mutual-visibility colouring with two colours is NP-complete for every fixed diameter
    Siddhesh Chaubal
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Deletion thresholds and exponential examples for complete sequences
    Jesse Geneson
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Every finite group admits a just finite presentation
    Marc Lackenby
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. On a finite group in which every non-supersolvable maximal subgroup is a TI-subgroup
    Jiangtao Shi, Fanghua Li
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026finite,
  title = {{Finite deletion-induced saturation for every non-complete graph}},
  author = {Haochen Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.21388},
  eprint = {2609.21388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.21388},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Finite deletion-induced saturation for every non-complete graph
AU  - Haochen Liu
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.21388
UR  - https://arxiv.org/abs/2609.21388
AB  - A graph G is deletion-induced-saturated for H if G has an edge, contains no induced copy of H, and deleting any edge of G creates an induced copy of H. We prove, with finite certificate verification, that a finite graph H admits such a finite graph G if and only if H is not complete. This resolves the deletion conjecture of Fan, Hajebi, Hajebi and Spirkl. The main step transfers suitable free amalgamations to finite extensions using a local lifting theorem of Auinger, Bitterlich and Otto. A second criterion treats edge addition by protecting specified nonedges and then taking a maximal induced-H-free completion. Structural results of Bonamy, Groenland, Johnston, Morrison and Scott reduce the remaining targets to dense templates and a finite hereditary class. Two uniform constructions in halved cubes handle the dense templates. The finite part is supported by exhaustive coverage certificates, structural certificates and explicit hosts, including a circulant graph on $30$ vertices.
ER  -