galvin_conflict_arc
def
Galvin's orientation of the conflict graph of a properly edge-coloured bipartite multigraph, in fibre form. Read f e as the left endpoint (part X) and g e as the right endpoint (part Y). Two edges conflict when they are distinct and share a left or a right endpoint. At a shared left endpoint arcs go from the larger colour m to the smaller; at a shared right endpoint from the smaller colour to the larger. On a pair of parallel edges (same f and same g) both disjuncts fire, so such a pair carries a digon -- this is deliberate and necessary.
Statement
def galvin_conflict_arc {α : Type*} (f g m : α → ℕ) (e₁ e₂ : α) : Prop
- Source
- step towards galvin_bipartite_multigraph_list_edge_colouring
- Verified
- 20 Oct 2026
- Axioms
- none listed
Lean source view module on GitHub
/-- Galvin's orientation of the line graph of a properly edge-coloured bipartite multigraph (f = left endpoint, g = right endpoint, digons kept on parallel edges). -/ def galvin_conflict_arc {α : Type*} (f g m : α → ℕ) (e₁ e₂ : α) : Prop := e₁ ≠ e₂ ∧ ((f e₁ = f e₂ ∧ m e₂ < m e₁) ∨ (g e₁ = g e₂ ∧ m e₁ < m e₂))