Degree-four vertex in non-4-colorable C₀ graphs
Conjecture 5 · arXiv:2504.08327
Status open high confidence
Conjecture 5 from arXiv:2504.08327 states that every non-4-colorable graph in the class C_0 has an internal vertex of degree four. The paper establishes that this conjecture is equivalent to the paper's main Conjecture 2 (that every graph of minimum degree five with no separating triangles drawn in the plane with one crossing is 4-colorable), and verifies both computationally for all graphs up to 28 vertices. The conjecture remains open in general; no follow-up paper resolving it was found in the literature.
Reviewer notes. No follow-up found. The paper is very recent (April 2025). Conjecture 5 is explicitly stated as open and equivalent to the main Conjecture 2. Computer enumeration verifies it for graphs up to 28 vertices. The structural reformulation via C_0 provides a combinatorially explicit analogue of how the Four Color Theorem reduces to triangulations.
Context
The class ${\cal C}_{0}\subseteq{\cal C}$ consists of graphs obtained from 4-connected plane triangulations by choosing two distinct facial triangles $xuv$ and $yuv$ sharing edge $uv$ and adding edge $xy$; vertices $x,y,u,v$ are external and all others internal. This conjecture is equivalent to Conjecture 2 (the main conjecture) and provides a more combinatorially explicit reformulation analogous to how the Four Color Theorem reduces to triangulations.
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