Extremal cone crossing number function

Problem 1 · arXiv:1608.07680

arXiv Problem high confidence— first stated 2016-08-27

Authors: Carlos A. Alfaro, Alan Arroyo, Marek Derunár, Bojan Mohar

Status partial high confidence

The problem asks for a general formula for f(k), the smallest crossing number achievable by the cone of any graph with crossing number at least k. The source paper (published as SIAM J. Discrete Math. 32 (2018) 2080–2093) establishes f(k) = k + Θ(√k) for multigraphs and computes the simple-graph version φ_s(3)=3, φ_s(4)=4, φ_s(5)=5. Ding and Huang (Graphs Combin. 2021) extend this table by proving φ_s(6)=5 and φ_s(7)=6. A closed-form formula for all k remains open.

Cited literature (1)

partial A Note on the Crossing Number of the Cone of a Graph (2021)

Ding, Z., Huang, Y. · Graphs and Combinatorics · doi:10.1007/s00373-021-02361-2

Proves φ_s(6) = 5 and φ_s(7) = 6 for simple graphs, extending the table of exact values of f(k) from the source paper.

Reviewer notes. The Ding-Huang 2021 follow-up paper (Graphs Combin. 37:2351-2363) is behind a paywall; its content was confirmed via multiple consistent search results. No arXiv preprint was found for that paper. The general formula for f(k) (or φ_s(k) in the simple-graph setting) for all k ≥ 0 remains open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. For each $k \geq 0$, find the smallest integer $f(k)$ for which there is a graph $G$ with crossing number at least $k$ and its cone has $\operatorname{cr}(CG) = f(k)$.

Context

Motivated by the negative answer to Richter's question for $n=6$, the authors reformulate the problem as finding the minimum possible crossing number of a cone over all graphs of a given crossing number. Equivalently, $f(k)$ is the largest integer such that every graph with $\operatorname{cr}(G) \geq k$ satisfies $\operatorname{cr}(CG) \geq f(k)$. The paper proves $f(k) = k + \Theta(\sqrt{k})$ for multigraphs.

Source paper

The crossing number of the cone of a graph
Carlos A. Alfaro, Alan Arroyo, Marek Derunár, Bojan Mohar · 2016-08-27
https://arxiv.org/abs/1608.07680 PDF source