3-Edge-Coloring Conjecture

Importance: High ✭✭✭
Subject: Graph Theory
Recomm. for undergrads: yes
Prize: no
Posted by: arthur
on: April 28th, 2020
Conjecture   Suppose $ G $ with $ |V(G)|>2 $ is a connected cubic graph admitting a $ 3 $-edge coloring. Then there is an edge $ e \in E(G) $ such that the cubic graph homeomorphic to $ G-e $ has a $ 3 $-edge coloring.

Reformulation via 4-flows:

Conjecture   Suppose $ G $ is a cubic graph with a nowhere-zero $ 4 $-flow, then there is an edge $ e \in E(G) $ such that $ G-e $ has a nowhere-zero $ 4 $-flow.

Bibliography



* indicates original appearance(s) of problem.