Skip to content
DraconiticResearch
Search Sources API
182,469 studies31 sourcesUpdated 37 min ago
PreprintCC BY 4.0arXiv

Extremal function for rooted K5 minors

  • Zdeněk Dvořák
Open at sourcePDFDOICite

Abstract

We show that if an n-vertex 5-connected graph has at least 4n-10 edges, then for any choice of five of its vertices, we can contract disjoint connected subgraphs containing these vertices to obtain K5 as a minor. The bound on the number of edges is the best possible.

Related

  1. An explicit bound on the extremal function for complete graph minors
    David R. Wood
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Rooted spanning forests in wheel graphs: Fibonacci-Lucas formulas and extremal root configurations
    Shunya Tamura, Yuuho Tanaka
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The Riemann zeta function at the zeros of real-rooted trigonometric polynomials
    Felipe Gonçalves, Bryce Kerr, Oleksiy Klurman +1
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryAnalysis & PDEsarXiv
  4. Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
    Angel Ivanov Raychev
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
    Dibyayan Chakraborty, Florent Foucaud
    HALPreprintLicence not statedCombinatorics & discrete mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{dvorak2026extremal,
  title = {{Extremal function for rooted $K_5$ minors}},
  author = {Zdeněk Dvořák},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.13818},
  eprint = {2609.13818},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13818},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Extremal function for rooted K_5 minors
AU  - Zdeněk Dvořák
PY  - 2026
DA  - 2026/09/12
PB  - arXiv
DO  - 10.48550/arxiv.2609.13818
UR  - https://arxiv.org/abs/2609.13818
AB  - We show that if an n-vertex 5-connected graph has at least 4n-10 edges, then for any choice of five of its vertices, we can contract disjoint connected subgraphs containing these vertices to obtain K_5 as a minor. The bound on the number of edges is the best possible.
ER  -