Optimal degree bounds for c-crossing-critical graphs

Optimal degree bounds $D_c$ for small $c$ · arXiv:1903.05363

arXiv Informal medium confidence— first stated 2021-05-05

Authors: Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, Tilo Wiedera

Status open high confidence

The conjecture asks to determine the optimal values $D_c$ for each $c \in \{2, 3, \ldots, 12\}$; the source paper establishes $D_1 = 4$, $D_2 \geq 8$, and notes that $D_2$ should be within reach via the Bokal–Oporowski–Richter–Salazar characterisation of large 2-crossing-critical graphs, while the remaining $D_c$ are left to future work. A 2021 arXiv preprint (2112.04854) establishes order, maximum degree, and other parameters of large 2-crossing-critical graphs and may implicitly yield $D_2$, but its abstract does not state a specific value. No paper published strictly after 2021 that resolves any optimal $D_c$ value for $c \in \{2, \ldots, 12\}$ was found in a broad web search.

Reviewer notes. No follow-up paper from 2022–2026 resolving any optimal $D_c$ value was found. arXiv:2112.04854 ('Properties of Large 2-Crossing-Critical Graphs', 2021) establishes the maximum degree of large 2-crossing-critical graphs and may yield $D_2$, but its abstract does not confirm a specific numerical value; it predates the published year threshold so is not listed in since_posted. arXiv:2105.01104 ('On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees', 2021) concerns $c \geq 13$ and is unrelated to the conjecture. The question of the exact optimal $D_c$ for $c \in \{2, \ldots, 12\}$ appears to remain open.

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

Informal. Determine the optimal values of $D_c$ for each $c \in \{2, 3, \ldots, 12\}$, where $D_c$ is the smallest integer such that every $c$-crossing-critical graph has maximum degree at most $D_c$.

Context

Theorem 1.1 guarantees the existence of finite bounds $D_c$ for each $c \leq 12$, but the proof is asymptotic and does not yield explicit values. The paper notes $D_1 = 4$, $D_2 \geq 8$, and that the optimal $D_2$ should be within reach using existing characterisation results, while the remaining bounds are left to future investigations.

Notes. Stated as a future-work direction rather than a formally labelled open problem; Section 7 (open problems) was not included in the provided text excerpt.

Source paper

Bounded maximum degree conjecture holds precisely for $c$-crossing-critical graphs with $c \leq 12$
Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, Tilo Wiedera · 2021-05-05
https://arxiv.org/abs/1903.05363 PDF source