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.


* indicates original appearance(s) of problem.


Is this conjecture missing some greater context? It seems obviously false on its own


wouldn't removing any edge from a cubic graph make the graph not cubic?

A counterexample?

What would be the cubic graph homeomorphic to K4-e? I think I can show there does not exist a cubic graph homeomorphic to K4-e. If so, this would seem to contradict the conjecture's claim.

Is there yet any progress on this problem?

Hello, I would like to know whether anybody made any progress on this. I tried to google and found nothing. Also, why is there nothing in Bibliography of this problem? Is there any paper involving or proposing it? Thanks in advance

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.