Home » Subject » Graph Theory

3-Edge-Coloring Conjecture

Importance: High ✭✭✭
Author(s): Arthur
Hoffmann-Ostenhof
Subject: Graph Theory
Keywords: 3-edge coloring
4-flow
removable edge
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.
add new comment

Context

On June 23rd, 2022 Anonymous says:

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

reply

question

On June 22nd, 2022 Anonymous says:

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

reply

A counterexample?

On August 3rd, 2021 Anonymous says:

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.

reply

Is there yet any progress on this problem?

On November 13th, 2020 Anonymous says:

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

reply

Comment viewing options

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