ProperlyColorsKColorable
def
For an integer k and graph size n, a coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors properly colors k-colorable graphs if for every simple graph G on Fin n such that G.Colorable k, for all u, v : Fin n, G.Adj u v implies A G u ≠ A G v.
Statement
def ProperlyColorsKColorable {n : ℕ} (k : ℕ) (A : SimpleGraph (Fin n) → (Fin n → ℕ)) : Prop
- Defined in
- arXiv:2610.41516 Section 1
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 3
- op869_online_coloring_clique_exactFor any natural number k, any coloring algorithm A : SimpleGraph (Fin k) → (Fin k → ℕ) that properly colors k-colorable graphs uses…
- op869_adversary_forces_soundA winning one-fold adversary position, whose recorded earlier colors agree with a proper online algorithm on the current predecessor…
- op869_three_colorable_bound_implies_deterministic_lower_boundIf the three-colorable deterministic online coloring lower bound of arXiv:2610.41516 Theorem 1.1 holds in the stated finite-graph model,…
Read back from the Lean
Given a natural number k and a function A that assigns to each simple graph on Fin n a vertex labeling Fin n → ℕ, ProperlyColorsKColorable k A asserts that for every simple graph G on vertices Fin n, if G is k-colorable, then for all vertices u, v : Fin n, if u is adjacent to v in G, then A G u ≠ A G v (that is, A G is a proper coloring of G).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A coloring algorithm on Fin n assigning natural number colors properly colors k-colorable graphs if it gives a proper coloring whenever G is k-colorable. -/ def ProperlyColorsKColorable {n : ℕ} (k : ℕ) (A : SimpleGraph (Fin n) → (Fin n → ℕ)) : Prop := ∀ (G : SimpleGraph (Fin n)), G.Colorable k → ∀ (u v : Fin n), G.Adj u v → A G u ≠ A G v