Degree-four vertex in 5-critical crossing graphs
Conjecture 1 · arXiv:2504.08327
Status open high confidence
Conjecture 1 from arXiv:2504.08327 asserts that every 5-critical graph in the class C of graphs drawable with at most one crossing contains a vertex of degree four; it serves as a stepping stone toward the stronger Conjecture 2 (4-colorability). The authors verify both conjectures computationally for all graphs with at most 28 vertices but give no general proof. No follow-up paper resolving Conjecture 1 was found in over a year of indexed literature.
Reviewer notes. No follow-up found. The conjecture is approximately 13 months old (posted April 2025). Class C is all graphs drawable in the plane with at most one crossing. The authors' own computer search confirms the conjecture for graphs up to 28 vertices. Conjecture 2, which implies Conjecture 1, is the main open problem of the paper.
Context
The authors observe that 5-critical graphs have minimum degree at least four and that there is a natural way to handle degree-four vertices: if $G\neq K_5$ is 5-critical and $v$ has degree four, one can find non-adjacent neighbours $x,y$ of $v$ and contract them. Conjecture 1 is stated as a stepping stone toward the main Conjecture 2, which implies it because 5-critical graphs contain no separating cliques.
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