Black and White Cycle Conjecture

Importance: High ✭✭✭
Subject: Graph Theory
» Coloring
» » Edge coloring
Recomm. for undergrads: yes
Posted by: arthur
on: September 21st, 2026
Conjecture   Let $ G $ be a cubic graph with a nz-$ 4 $-flow, and let each edge $ e \in E(G) $ satisfying $ G-e $ does not have a nz-$ 4 $-flow be colored black, and let each edge $ e \in E(G) $ satisfying $ G-e $ has a nz-$ 4 $-flow be colored white. Then $ G $ contains a white cycle but not a black cycle.


Used terminology: nz-$ 4 $-flow is the abbrevation for nowhere-zero $ 4 $-flow, a cycle is a connected $ 2 $-regular graph, a cycle is called black (white) if each edge of the cycle is colored black (white).


Bibliography



* indicates original appearance(s) of problem.