Restricted 4-coloring instances and finite encodings
DefinitionFasterExactColoring_ThreeColor_Supplement_RestrictedLet be a finite simple undirected graph with vertices . A restricted instance is , with disjoint vertex sets , where is independent and every neighbor of belongs to . Put . A valid coloring is a proper four-coloring assigning color on and one of colors on ; vertices of may use all four colors.
The component sets, numbers , initial instance , and children are computed from this data. The graph and both subsets have explicit finite encodings. These objects support every Section 5 algorithm without imposing terminality on the headline theorems.
Formalization Note The published graph model is reused. Colors are numbered in Lean, so the distinguished color is . Connected components are the distinct bounded flood-fill sets starting at vertices of ; the empty set contributes no component. The original graph and its vertex order are retained by every child.
import Mathlib
import Definitions.Def_FasterExactColoring_ThreeColor_GraphInput
set_option autoImplicit false
namespace FasterExactColoring.ThreeColor.Supplement
/-- Section 5.1: the graph is retained throughout the branching tree. -/
structure Restricted (n : ℕ) where
G : GraphInput n
I : Finset (Fin n)
S : Finset (Fin n)
def Restricted.U {n : ℕ} (P : Restricted n) : Finset (Fin n) :=
vertices \ (P.I ∪ P.S)
def Restricted.valid {n : ℕ} (P : Restricted n) : Prop :=
Disjoint P.I P.S ∧
(∀ u ∈ P.I, ∀ v ∈ P.I, ¬ P.G.graph.Adj u v) ∧
∀ u ∈ P.I, ∀ v, P.G.graph.Adj u v → v ∈ P.S
def Restricted.colorable {n : ℕ} (P : Restricted n) : Prop :=
∃ f : Fin n → Fin 4, properColoring P.G f ∧
(∀ v ∈ P.I, f v = 3) ∧ (∀ v ∈ P.S, (f v).val < 3)
def Restricted.code {n : ℕ} (P : Restricted n) : List ℕ :=
graphCode P.G ++ vertexSetCode P.I ++ vertexSetCode P.S
def initial {n : ℕ} (G : GraphInput n) : Restricted n := ⟨G, ∅, ∅⟩
def clique {n : ℕ} (G : GraphInput n) (C : Finset (Fin n)) (m : ℕ) : Prop :=
C.card = m ∧ ∀ u ∈ C, ∀ v ∈ C, u ≠ v → G.graph.Adj u v
def Restricted.components {n : ℕ} (P : Restricted n) : Finset (Finset (Fin n)) :=
P.U.image (component P.G P.U)
noncomputable def Restricted.cliques {n : ℕ} (P : Restricted n) (m : ℕ) :
Finset (Finset (Fin n)) := by
classical
exact P.components.filter (fun C => clique P.G C m)
noncomputable def Restricted.nClique {n : ℕ} (P : Restricted n) (m : ℕ) : ℕ :=
(P.cliques m).card
def Restricted.terminal {n : ℕ} (P : Restricted n) : Prop :=
∀ C ∈ P.components, clique P.G C 3 ∨ clique P.G C 4
/-- Children are changes of I,S on exactly the same graph. -/
def child {n : ℕ} (P : Restricted n) (IS : Finset (Fin n) × Finset (Fin n)) :
Restricted n := ⟨P.G, IS.1, IS.2⟩
def childrenCode {n : ℕ} (L : List (Finset (Fin n) × Finset (Fin n))) : List ℕ :=
L.length :: L.flatMap (fun IS => vertexSetCode IS.1 ++ vertexSetCode IS.2)
end FasterExactColoring.ThreeColor.Supplement