4-colorability with one crossing, degree ≥ 5

Conjecture 2 · arXiv:2504.08327

arXiv Conjecture high confidence— first stated 2025-04-14

Authors: Zdeněk Dvořák, Bernard Lidický, Bojan Mohar

Status open high confidence

Conjecture 2 from arXiv:2504.08327 remains open. The authors verify it computationally for all graphs with at most 28 vertices and prove it implies their Conjecture 1 (on 5-critical graphs with one crossing). No follow-up paper resolving the conjecture in either direction was found in indexed literature as of May 2026.

Reviewer notes. No follow-up found after five web calls. The conjecture is recent (April 2025). The paper establishes: (i) computer verification for all graphs up to 28 vertices; (ii) Conjecture 2 implies Conjecture 1; (iii) equivalence with precoloring extension problems in plane graphs with four-cycle outer faces (Theorem 10); (iv) a structural characterisation of non-4-colorable graphs in the class assuming the conjecture (Theorem 6). The separating-triangle-free assumption is noted to be necessary.

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

Conjecture. If a graph $G$ does not contain separating triangles and has a drawing in the plane with one crossing such that all vertices not incident with the crossed edges have degree at least five, then $G$ is 4-colorable.

Context

This is the central conjecture of the paper. The authors verify it by computer enumeration for all graphs with at most 28 vertices, prove that it implies Conjecture 1, and note that the assumption on separating triangles is necessary. It generalises the Four Color Theorem to graphs drawable with one crossing under a minimum-degree condition.

Source paper

On a conjecture concerning 4-coloring of graphs with one crossing
Zdeněk Dvořák, Bernard Lidický, Bojan Mohar · 2025-04-14
https://arxiv.org/abs/2504.08327