Crossing number of Kₙ minus t-matching
Conjecture 5 · arXiv:2009.03418
Status open medium confidence
Conjecture 5 from arXiv:2009.03418 posits that the crossing number of $M_{n,t}$ (the complete graph $K_n$ minus a matching of size $t$) equals $H(n) - \frac{1}{2}t(k-1)(k-2)$ where $k=\lfloor n/2\rfloor$. Mohar proves a matching upper bound via geodesic drawings built from strength-0 point sets, making the conjecture that this count is optimal. No paper resolving or making substantial progress on this specific conjecture was found in web searches; the underlying Hill conjecture for $K_n$ itself remains open, making resolution of this generalization unlikely to have been achieved unnoticed.
Reviewer notes. No follow-up paper specifically addressing Conjecture 5 of arXiv:2009.03418 was found. The conjecture is a natural extension of the long-standing open Hill conjecture (cr(K_n) = H(n)), which itself remains unresolved; the upper bound matching the conjectured value is established by Mohar via geodesic drawings of K_n minus a matching using strength-0 configurations. The paper appeared in a Springer proceedings volume (Graph Drawing 2020). Confidence is medium rather than high because the conjecture is ~6 years old and absence of web evidence for a conjecture with this level of notoriety is slightly suspicious, though consistent with the broader open status of Hill-type problems.
Context
Here $M_{n,t}$ denotes the graph obtained from $K_n$ by removing a matching of size $t$, and $k = \lfloor n/2 \rfloor$. Corollary 4 shows that geodesic drawings of $M_{n,t}$ built from sets of strength $0$ achieve this crossing count; the existence of many such sets of strength $0$ motivates the conjecture that this value is optimal.
Notes. PDF source; the algebraic expression is unambiguous.
Source paper
On a conjecture by Anthony Hill
Bojan Mohar · 2020-09-07
https://arxiv.org/abs/2009.03418
PDF source