Cut-based star edge-coloring extension (Lemma 4.2(b))
ProvedOPG37271.isStarEdgeColoring_insert_cutcombinatoricsedge-coloringgraph-theory
Let and let be the set of edges between and . Suppose that an edge-coloring of restricts to a star edge-coloring on both and , that no two distinct edges in share an endpoint in or have adjacent endpoints in , that every edge receives a color distinct from all edges () at distance at most from in , and that every edge in receives a color distinct from every edge in . 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_cut {V : Type u} {G : SimpleGraph V} {K : Type*}
(A : V → Prop) (c : EdgeColoring G K)
(hcA : IsStarEdgeColoring (fun e => c ⟨Sym2.map Subtype.val e.1, by rcases e with ⟨⟨a, b⟩, hab⟩; exact hab⟩ :
EdgeColoring (G.induce {v | A v}) K))
(hcB : IsStarEdgeColoring (fun e => c ⟨Sym2.map Subtype.val e.1, by rcases e with ⟨⟨a, b⟩, hab⟩; exact hab⟩ :
EdgeColoring (G.induce {v | ¬ A v}) K))
(hX_sep : ∀ u₁ v₁ u₂ v₂ : V,
G.Adj u₁ v₁ → A u₁ → ¬ A v₁ →
G.Adj u₂ v₂ → A u₂ → ¬ A v₂ →
s(u₁, v₁) ≠ s(u₂, v₂) →
u₁ ≠ u₂ ∧ ¬ G.Adj u₁ u₂)
(hX_B : ∀ u₁ v₁ x y : V,
(h1 : G.Adj u₁ v₁) → A u₁ → ¬ A v₁ →
(hxy : G.Adj x y) → (¬ A x ∨ ¬ A y) → s(x, y) ≠ s(u₁, v₁) →
(x = u₁ ∨ x = v₁ ∨ y = u₁ ∨ y = v₁ ∨
(G.Adj u₁ x ∧ ¬ A x) ∨ G.Adj v₁ x ∨ (G.Adj u₁ y ∧ ¬ A y) ∨ G.Adj v₁ y) →
c.get x y hxy ≠ c.get u₁ v₁ h1)
(hX_A : ∀ u₁ v₁ x y : V,
(h1 : G.Adj u₁ v₁) → A u₁ → ¬ A v₁ →
(hxy : G.Adj x y) → A x → A y →
c.get x y hxy ≠ c.get u₁ v₁ h1) :
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(b).