Skip to content
DraconiticResearch
Search Sources API
201,642 studies31 sourcesUpdated 11 min ago
PreprintarXiv licencearXiv

On Erdős Problem 767: Cycles with Chords

  • Xiaozheng Chen
  • Bo Ning
Open at sourcePDFDOICite

Abstract

For integers k≥ 1 and n≥ k+2, let gk(n) be the maximum number of edges in an n-vertex graph containing no cycle with a vertex incident with at least k chords. Erdős conjectured that gk(n)=(k+1)(n−k−1) for n≥ 2k+2. Lewin found a counterexample. Bollobás later conjectured that there exists a function n(k) such that gk(n)=(k+1)(n−k−1) for all n≥ n(k). Jiang confirmed this by proving the formula for all n≥3k+3 when k≥1. In this paper, we determine gk(n) completely. For all k≥1 and n≥ k+2, we prove gk(n)={⌊((k+1)n)/2⌋,max{a(n−a)+⌊(a(k+1−a))/2⌋ : a∈ℤ, ⌊ (k+1)/2⌋+1≤ a≤ k+1}}. For k≥2, we prove gk(n)=(k+1)(n−k−1) when n≥ ⌈(5k+1)/2⌉, and this threshold is sharp. Our proof builds on the method developed by Ma and the second author in [Ma and Ning, 2020].

Related

  1. Erdös–Pósa property of cycles that are far apart
    Vida Dujmović, Gwenaël Joret, Piotr Micek +1
    Journal of the London Mathematical SocietyPeer-reviewedLicence not statedFull text10 citedCombinatorics & discrete mathematicsOpenAlex
  2. An Erdős-Pósa theorem for induced packings of even cycles
    Jungho Ahn, Lars Jaffke, O-joung Kwon +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs
    Chengli Li, Bo Ning
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles
    Shuyan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
    Andrey Kupavskii, Fedor Noskov
    Forum of Mathematics, SigmaPeer-reviewedCC BY 4.0General mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{chen2026erdős,
  title = {{On Erdős Problem 767: Cycles with Chords}},
  author = {Xiaozheng Chen and Bo Ning},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.15330},
  eprint = {2609.15330},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.15330},
}
RIS
TY  - UNPB
TI  - On Erdős Problem 767: Cycles with Chords
AU  - Xiaozheng Chen
AU  - Bo Ning
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.15330
UR  - https://arxiv.org/abs/2609.15330
AB  - For integers k≥ 1 and n≥ k+2, let g_k(n) be the maximum number of edges in an n-vertex graph containing no cycle with a vertex incident with at least k chords. Erdős conjectured that g_k(n)=(k+1)(n−k−1) for n≥ 2k+2. Lewin found a counterexample. Bollobás later conjectured that there exists a function n(k) such that g_k(n)=(k+1)(n−k−1) for all n≥ n(k). Jiang confirmed this by proving the formula for all n≥3k+3 when k≥1. In this paper, we determine g_k(n) completely. For all k≥1 and n≥ k+2, we prove g_k(n)={⌊((k+1)n)/2⌋,max{a(n−a)+⌊(a(k+1−a))/2⌋ : a∈ℤ, ⌊ (k+1)/2⌋+1≤ a≤ k+1}}. For k≥2, we prove g_k(n)=(k+1)(n−k−1) when n≥ ⌈(5k+1)/2⌉, and this threshold is sharp. Our proof builds on the method developed by Ma and the second author in [Ma and Ning, 2020].
ER  -