graph_mutual_visibility_chromatic_number
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
- graph_is_mutual_visibility_colorableA simple graph G is mutual-visibility n-colorable if there exists a coloring of the vertices of G with n colors such that every color…
- Used by 3
- graph_11_mutual_visibility_chromatic_number_eq_threeThe simple graph G_11 has mutual-visibility chromatic number 3, chromatic number 3, and diameter 2.
- graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_twoFor every finite simple graph G of diameter 2, the mutual-visibility chromatic number of G is at most the chromatic number of G.
- exists_diameter_two_graph_mutual_visibility_chromatic_number_threeThere exists a finite connected simple graph G of diameter 2 such that the mutual-visibility chromatic number of G equals 3 and the…
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 : ℕ∞)