AFTD Auto-Formalizing Theoretical Domains

graph_mutual_visibility_chromatic_number

def

The mutual-visibility chromatic number of a simple graph G is the infimum in ℕ∞ of the natural numbers n such that G is mutual-visibility n-colorable.

Statement

noncomputable def graph_mutual_visibility_chromatic_number {V : Type*} (G : SimpleGraph V) : ℕ∞
Defined in
arXiv:2610.39430, Definition 1.1
Verified
30 Oct 2026
Axioms
none listed
Built on 1
Used by 3

Read back from the Lean

For a type V and a simple graph G on V, graph_mutual_visibility_chromatic_number G is the infimum in ℕ∞ (extended natural numbers, with ⊤ if the set is empty) of all n : ℕ such that G is mutual-visibility colorable with n colors. Here, G is mutual-visibility colorable with n colors (graph_is_mutual_visibility_colorable G n) if there exists a coloring c : V → Fin n such that each color class {v : V | c v = i} (for each i : Fin n) is a mutual-visibility set. A set S : Set V is a mutual-visibility set (graph_is_mutual_visibility_set G S) if for all u ∈ S and v ∈ S, there exists a walk p from u to v in G whose length equals the graph distance G.dist u v (i.e., a shortest path), such that every vertex x in the vertex sequence of p (p.support) that belongs to S is either u or v (i.e., no other vertex of S lies on the path).

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

/-- The mutual-visibility chromatic number χ_μ(G) is the minimum number of mutual-visibility sets partitioning V(G). -/
noncomputable def graph_mutual_visibility_chromatic_number {V : Type*} (G : SimpleGraph V) : ℕ∞ := ⨅ n ∈ {n : ℕ | graph_is_mutual_visibility_colorable G n}, (n : ℕ∞)
See it in the graphDiscuss this resultChallenge it