Home » Subject » Graph Theory
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.
4 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options