Safe edge and borrowed color selection on a 5-cycle (Cases 1 & 2)
ProvedOPG37271.exists_five_cycle_safe_edge_colorcombinatoricsedge-coloringgraph-theory
Let the vertices of a -cycle carry optional colors such that adjacent vertices never carry the same color, and let be a list of at most two vertex-color conflict pairs . Then there exists an edge of and a color such that no vertex of carries , and no conflict pair with has .
Preamble
import Mathlib.Data.Fintype.Card namespace OPG37271
Formal statement
theorem exists_five_cycle_safe_edge_color
(f : Fin 5 → Option (Fin 4))
(hadj : ∀ i : Fin 5, f i ≠ none → f i ≠ f (i + 1))
(X : List (Fin 5 × Fin 4))
(hX : X.length ≤ 2) :
∃ (e : Fin 5) (col : Fin 4),
(∀ u : Fin 5, u ≠ e + 3 → f u ≠ some col) ∧
(∀ p ∈ X, (p.1 = e ∨ p.1 = e + 1) → p.2 ≠ col) := by sorry
end OPG37271Source
Dvořák, Mohar, and Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313–326 (arXiv:1011.3376), Section 4, proof of Theorem 4.1(a) (5-cycle Cases 1 and 2).