Theorem 1.3 (companion theorem; not used in the proof of the goal) — deterministic four-coloring
OpenFasterExactColoring.ThreeColor.Supplement.deterministic_four_coloringexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is one deterministic finite program deciding whether any finite simple undirected graph on vertices admits a proper four-coloring. For fixed constants , independent of the graph and its order, its charged worst-case time is at most
The graph may be empty, disconnected, or have arbitrary degrees. No terminal-instance, packing, measure-weight or numerical-certificate assumption appears in this theorem. This is the deterministic four-coloring companion result.
Differences from the source:
- encoding: arbitrary finite simple undirected graphs and O* running time → Fin n graph inputs and one charged finite program with C>0 and d in Nat before every n and G; reason: finite labels and uniform polynomial overhead express the same decision bound; empty graphs are included
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_Certificates set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem deterministic_four_coloring :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
graphSolver .det 4 A C d (679/400 : ℝ) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Theorem 1.3, p. 1 (PDF p. 3)