A linear bound for nested cycles without geometric crossings
Cycles $C_1,\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\subseteq\cdots\subseteq V(C_1)$, and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let $f_k(n)$ be the least number of edges that forces such a family in every $n$-vertex graph. Gil Fernández, Kim, Kim and Liu proved that $f_2(n)=O(n)$, answering a question of Erdős, and asked whether $f_k(n)=O_k(n)$ for every fixed $k$. We prove this for all $k$. The proof selects the inner cycles together with a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.02234
curl -X POST /api/v1/records/arxiv/2609.02234/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.02234/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'