Tutte's 4-flow Conjecture (1966)

Originator(s): William Tutte (U. Waterloo)

Conjecture/Question: Every bridgeless graph containing no subdivision of the Petersen graph is 4-flowable [T2].

Definitions/Background/motivation: A bridgeless graph is a graph with no cut-edge.

Comments/Partial results: For 3-regular graphs, the statement is equivalent to the statement that 3-regular graphs containing no subdivision of the Petersen graph are 3-edge-colorable, which was proved in a series of papers by Robertson, Sanders, Seymour, and Thomas.

Tutte [1954] proved that every graph having a k-face-colorable 2-cell embedding on some orientable surface also has a nowhere-zero k-flow; indeed, for planar graphs, the 4-flow Conjecture is equivalent to the Four Color Theorem.


Back to Index Page Link to Glossary