simple_graph_coloring_is_achromatic
def
A 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 distinct colour classes.
Statement
def simple_graph_coloring_is_achromatic {V : Type*} {G : SimpleGraph V} {k : ℕ} (C : G.Coloring (Fin k)) : Prop
- Defined in
- arXiv:2610.27510 (The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs), Sec. 1, definition of an achromatic colouring
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 6
- 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).
- simple_graph_achromatic_numberχ_a(G) is the maximum number of colours in an achromatic colouring of G.
- 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
/-- A proper colouring with colours `Fin k` is achromatic (complete) if every colour is used and every two distinct colour classes are joined by an edge. -/ def simple_graph_coloring_is_achromatic {V : Type*} {G : SimpleGraph V} {k : ℕ} (C : G.Coloring (Fin k)) : Prop := Function.Surjective C ∧ ∀ i j : Fin k, i ≠ j → ∃ u v, G.Adj u v ∧ C u = i ∧ C v = j