Reducibility of Figure 1(b) (triangle with two degree-2 stems)
ProvedOPG37271.hasStarEdgeColoring_of_auxreduc_2combinatoricsedge-coloringgraph-theory
Let be a finite subcubic simple graph containing distinct vertices forming a triangle with stem edges and , where , , and is independent. 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_2 {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₂) (h20 : G.Adj a₂ a₀)
(h13 : G.Adj a₁ a₃) (h24 : G.Adj a₂ a₄)
(ha₃ : (G.neighborSet a₃).encard ≤ 2) (ha₄ : (G.neighborSet a₄).encard ≤ 2)
(hna03 : ¬ G.Adj a₀ a₃) (hna04 : ¬ 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 (second configuration).