simple_graph_achromatic_number
def
χ_a(G) is the maximum number of colours in an achromatic colouring of G.
Statement
noncomputable def simple_graph_achromatic_number {V : Type*} (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2610.27510 (The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs), Sec. 1, definition of χ_a
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- simple_graph_coloring_is_achromaticA proper vertex colouring with k colours is achromatic if all k colours are used and there is at least one edge between each pair of…
- Used by 5
- cubic_paley_graph_zmod_nineteen_achromatic_numberThe cubic Paley graph G_3(19) has achromatic number 9 = (19 − 1)/2, the upper bound, above the value (19 + 2)/3 = 7 conjectured for large q.
- simple_graph_achromatic_number_le_max_degree_or_halfFor every finite graph, χ_a(G) ≤ max{Δ(G) + 1, ⌊n/2⌋}: if some colour class is a single vertex, that vertex has a neighbour in each of the…
- le_simple_graph_achromatic_numberAn achromatic colouring with k colours shows χ_a(G) ≥ k (the set of such k is bounded by |V| since achromatic colourings are surjective).
- cubic_paley_graph_zmod_thirteen_achromatic_numberThe cubic Paley graph G_3(13) has achromatic number 6 = (13 − 1)/2, the upper bound, above the value (13 + 2)/3 = 5 conjectured for large q.
- cubic_paley_graph_zmod_thirty_one_achromatic_numberThe cubic Paley graph G_3(31) has achromatic number 15 = (31 − 1)/2, the upper bound, above the value (31 + 2)/3 = 11 conjectured for…
Lean source view module on GitHub
/-- The achromatic number χ_a(G): the largest number of colours in an achromatic colouring. -/ noncomputable def simple_graph_achromatic_number {V : Type*} (G : SimpleGraph V) : ℕ := sSup {k : ℕ | ∃ C : G.Coloring (Fin k), simple_graph_coloring_is_achromatic C}