Lemma 5.1 (used in the proof of Theorem 1.3) — maximal-star degree consequences
OpenFasterExactColoring.ThreeColor.Supplement.maximal_star_consequencesexact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any valid terminal restricted four-coloring instance, with . Supply the two inclusion-maximal vertex-disjoint packings of Section 5.2, and use as defined there. Both conclusions hold:
The first conclusion is pointwise at each vertex, so it also covers the empty induced graph. Stars are subgraphs and need not be induced. These are the degree restrictions required by the terminal decomposition algorithms.
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_StarPackings set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement
theorem maximal_star_consequences {n : ℕ} (P : Restricted n) (K : StarPackings n)
(hP : P.valid) (ht : P.terminal) (hK : K.valid P) :
(∀ v ∈ P.S \ K.firstVertices, degreeIn P.G (P.S \ K.firstVertices) v ≤ 2) ∧
(∀ u ∈ P.U \ K.secondCenters, degreeIn P.G (K.remainingS P) u ≤ 2) := by sorry
end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.1, p. 10 (PDF p. 12)