Star edge-coloring extension when fewer than k edges lie within distance 2
ProvedOPG37271.hasStarEdgeColoring_of_dist_le_two_ltcombinatoricsedge-coloringgraph-theory
Let be a simple graph and an edge of . Suppose admits a star -edge-coloring, and the set of edges in at edge-distance at most from can be covered by a finite set of cardinality . Then also admits a star -edge-coloring.
Preamble
import Definitions.Def_opg37271_star_edge_coloring import Mathlib.Combinatorics.SimpleGraph.DeleteEdges universe u namespace OPG37271
Formal statement
theorem hasStarEdgeColoring_of_dist_le_two_lt {V : Type u} {G : SimpleGraph V} {k : ℕ}
(u v : V) (huv : G.Adj u v)
(hc' : HasStarEdgeColoring (G.deleteEdges {s(u, v)}) k)
(hbound : ∃ S : Finset (Sym2 V), S.card < k ∧
∀ x y : V, 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) →
s(x, y) ∈ S) :
HasStarEdgeColoring G k := by sorry
end OPG37271Source
Dvořák, Mohar, and Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313–326 (arXiv:1011.3376), Section 4, immediate consequence of Lemma 4.2(a).