Star 7-edge-coloring for reduced bridgeless subcubic simple graphs
OpenOPG37271.subcubic_seven_color_of_reducedcombinatoricsedge-coloringgraph-theory
Every finite bridgeless subcubic simple graph with no adjacent vertices of degree at most and no degree- vertex whose neighbors are adjacent 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 subcubic_seven_color_of_reduced {V : Type u} [Fintype V] (G : SimpleGraph V)
(hsub : IsSubcubic G)
(hbridgeless : ∀ u v : V, G.Adj u v → (G.deleteEdges {s(u, v)}).Reachable u v)
(hnoadj2 : ∀ u v : V, G.Adj u v → ¬ ((G.neighborSet u).encard ≤ 2 ∧ (G.neighborSet v).encard ≤ 2))
(hnotri2 : ∀ x y z : V, G.Adj x z → G.Adj y z → G.Adj x y → ¬ (G.neighborSet z).encard ≤ 2) :
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, Theorem 4.1(a).