Reducibility of Figure 1(a) (4-cycle with stem and two degree-2 vertices)
ProvedOPG37271.hasStarEdgeColoring_of_auxreduc_1combinatoricsedge-coloringgraph-theory
Let be a finite subcubic simple graph containing distinct vertices forming a -cycle plus a stem edge , with , , and no chords among . If admits a star -edge-coloring, then so does .
Preamble
import Definitions.Def_opg37271_star_edge_coloring import Mathlib.Combinatorics.SimpleGraph.DeleteEdges universe u namespace OPG37271
Formal statement
theorem hasStarEdgeColoring_of_auxreduc_1 {V : Type u} [Fintype V] {G : SimpleGraph V}
(hsub : IsSubcubic G) (a₀ a₁ a₂ a₃ a₄ : V)
(hnd : [a₀, a₁, a₂, a₃, a₄].Nodup)
(h01 : G.Adj a₀ a₁) (h12 : G.Adj a₁ a₂) (h23 : G.Adj a₂ a₃) (h30 : G.Adj a₃ a₀)
(h24 : G.Adj a₂ a₄)
(ha₀ : (G.neighborSet a₀).encard ≤ 2) (ha₄ : (G.neighborSet a₄).encard ≤ 2)
(hna13 : ¬ G.Adj a₁ a₃) (hna14 : ¬ G.Adj a₁ a₄) (hna34 : ¬ G.Adj a₃ a₄)
(hc' : HasStarEdgeColoring
(G.deleteEdges {e : Sym2 V | a₀ ∈ e ∨ a₁ ∈ e ∨ a₂ ∈ e ∨ a₃ ∈ e ∨ a₄ ∈ e}) 7) :
HasStarEdgeColoring G 7 := by sorry
end OPG37271Source
Dvořák, Mohar, and Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313–326 (arXiv:1011.3376), Section 4, Figure 1 (first configuration).