Reducibility of adjacent vertices of degree at most 2 in star 7-edge-coloring
ProvedOPG37271.hasStarEdgeColoring_of_adj_deg_le_twocombinatoricsedge-coloringgraph-theory
Let be a finite subcubic simple graph containing an edge whose endpoints both have degree at most in . 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_adj_deg_le_two {V : Type u} [Fintype V] {G : SimpleGraph V}
(hsub : IsSubcubic G) (u v : V) (huv : G.Adj u v)
(hu2 : (G.neighborSet u).encard ≤ 2) (hv2 : (G.neighborSet v).encard ≤ 2)
(hc' : HasStarEdgeColoring (G.deleteEdges {s(u, v)}) 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) (adjacent degree-2 vertices reduction).