Skip to content
DraconiticResearch
Search Sources API
186,541 studies31 sourcesUpdated 41 min ago
PreprintCC BY 4.0arXiv

A sharp density bound for 5-connected graphs with no Ke minor

  • Caibing Chang
  • Zijian Deng
  • Qinfei Tang
  • Caihong Yang
Open at sourcePDFDOICite

Abstract

Let Ke be obtained from K7 by deleting two independent edges. We prove that every 5-connected graph on n≥7 vertices with at least 4n−9 edges contains a Ke minor, settling Conjecture~1.4 of Dvo\v rák, Norin and Rahman (arXiv preprint 2609.17760v1). The bound is sharp. We prove the stronger statement that every $4$-bilight graph on n≥4 vertices with at least 4n−9 edges contains either a Ke minor or a K6 subgraph. Within their reduction framework, we strengthen the rooted-minor theorem. We show that every $4$-light 5-rooted graph of rooted $4$-density at least two has a model with two nonroot vertices and at most one missing edge incident with them. At the critical density, reductions preserve density exactly, which prevents them from creating a new K6 subgraph.

Related

  1. A proof of the maximum Laplacian energy conjecture for connected graphs via a sharp eigenvalue-sum bound
    Seyed Ahmad Mojallal
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A note on highly connected K2,ℓ -minor free graphs
    Nicolas Bousquet, Théo Pierron, Alexandra Wesolek
    Discrete MathematicsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsHAL
  3. An improved bound on the treewidth of planar graphs excluding a grid minor
    Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A sharp density bound for infinite convolutions
    Peio Alcorta
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. A sharp bound on the binding number of Kk-free graphs and the Brandt conjecture
    Jifu Lin, Heng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chang2026sharp,
  title = {{A sharp density bound for 5-connected graphs with no $\Ke$ minor}},
  author = {Caibing Chang and Zijian Deng and Qinfei Tang and Caihong Yang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26041},
  eprint = {2609.26041},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26041},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A sharp density bound for 5-connected graphs with no Ke minor
AU  - Caibing Chang
AU  - Zijian Deng
AU  - Qinfei Tang
AU  - Caihong Yang
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26041
UR  - https://arxiv.org/abs/2609.26041
AB  - Let Ke be obtained from K_7 by deleting two independent edges. We prove that every 5-connected graph on n≥7 vertices with at least 4n−9 edges contains a Ke minor, settling Conjecture~1.4 of Dvo\v rák, Norin and Rahman (arXiv preprint 2609.17760v1). The bound is sharp. We prove the stronger statement that every $4$-bilight graph on n≥4 vertices with at least 4n−9 edges contains either a Ke minor or a K_6 subgraph. Within their reduction framework, we strengthen the rooted-minor theorem. We show that every $4$-light 5-rooted graph of rooted $4$-density at least two has a model with two nonroot vertices and at most one missing edge incident with them. At the critical density, reductions preserve density exactly, which prevents them from creating a new K_6 subgraph.
ER  -