On Erdős Problem 767: Cycles with Chords
For integers $k\ge 1$ and $n\ge 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\ge 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\ge n(k)$. Jiang confirmed this by proving the formula for all $n\ge3k+3$ when $k\ge1$. In this paper, we determine $g_k(n)$ completely. For all $k\ge1$ and $n\ge k+2$, we prove…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.15330
curl -X POST /api/v1/records/arxiv/2609.15330/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.15330/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'