Lemma 5.5 (used in the proof of Theorem 1.3) — tree-DP terminal algorithm
OpenFasterExactColoring.ThreeColor.Supplement.tree_terminal_algorithmexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There are one deterministic finite program and constants deciding every valid terminal restricted four-coloring instance with its valid maximal star packings in a polynomial in its full encoded size times
The quantities count the vertices in the first packing and the triangle and four-clique components of . Correctness respects every edge, including edges between precolored vertices. This terminal bound complements the CSP and three-coloring alternatives.
Differences from the source:
- encoding: terminal instances after the two maximal-star preprocessing steps → valid restricted instances with supplied valid inclusion-maximal star packings, all structural counts computed from them; reason: the explicit finite input includes the graph, restrictions and packings; its size is polynomial in the original vertex count
Preamble
import Mathlib import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TerminalBounds set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem tree_terminal_algorithm :
∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
terminalSolver .det A C d (fun P K => treeTerminalFactor P K) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.5, p. 13 (PDF p. 15)