Single-edge star edge-coloring extension (Lemma 4.2(a))
ProvedOPG37271.isStarEdgeColoring_insert_edgecombinatoricsedge-coloringgraph-theory
Let be a simple graph, an edge of , and a -edge-coloring of . Suppose that the restriction of to is a star edge-coloring, and that for every edge at edge-distance at most from (meaning shares an endpoint with or has an endpoint adjacent to an endpoint of ). Then is a star edge-coloring of .
Preamble
import Definitions.Def_opg37271_star_edge_coloring import Mathlib.Combinatorics.SimpleGraph.DeleteEdges universe u namespace OPG37271
Formal statement
theorem isStarEdgeColoring_insert_edge {V : Type u} {G : SimpleGraph V} {K : Type*}
(u v : V) (huv : G.Adj u v) (c : EdgeColoring G K)
(hc_rest : IsStarEdgeColoring (fun e => c ⟨e.1, SimpleGraph.edgeSet_mono (SimpleGraph.deleteEdges_le {s(u, v)}) e.2⟩ :
EdgeColoring (G.deleteEdges {s(u, v)}) K))
(hdist : ∀ (x y : V) (hxy : G.Adj x y), s(x, y) ≠ s(u, v) →
(x = u ∨ x = v ∨ y = u ∨ y = v ∨ G.Adj u x ∨ G.Adj v x ∨ G.Adj u y ∨ G.Adj v y) →
c.get x y hxy ≠ c.get u v huv) :
IsStarEdgeColoring c := by sorry
end OPG37271Source
Dvořák, Mohar, and Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313–326 (arXiv:1011.3376), Lemma 4.2(a).