Reducibility of a 4-vertex path with degree-2 endpoints (distinct boundary)
ProvedOPG37271.hasStarEdgeColoring_of_deg2_path4_distinctcombinatoricsedge-coloringgraph-theory
Let be a finite subcubic simple graph containing a path where and , and suppose the eight boundary vertices (with ) are pairwise distinct. If admits a star -edge-coloring, 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_deg2_path4_distinct {V : Type u} [Fintype V]
{G : SimpleGraph V} (hsub : IsSubcubic G) (w x y z w' x' y' z' : V)
(hnd : [w, x, y, z, w', x', y', z'].Nodup)
(hwx : G.Adj w x) (hxy : G.Adj x y) (hyz : G.Adj y z)
(hww' : G.Adj w w') (hxx' : G.Adj x x') (hyy' : G.Adj y y') (hzz' : G.Adj z z')
(hw2 : (G.neighborSet w).encard ≤ 2) (hz2 : (G.neighborSet z).encard ≤ 2)
(hc' : HasStarEdgeColoring (G.deleteEdges {s(w, x), s(x, y), s(y, z)}) 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, proof of Theorem 4.1(a) (Figure 2 / Cases 1–4).