TOPICS
Search

Tutte Three-Edge-Coloring Conjecture

The Tutte three-edge-coloring conjecture asserts that every biconnected cubic graph without the Petersen graph as a graph minor has edge chromatic number 3. It is also commonly phrased as the assertion that every snark has the Petersen graph as a graph minor. The conjecture is the cubic-graph special case of the Tutte 4-flow conjecture (Tutte 1966, Inoue et al. 2026).

Robertson et al. (1997, 2019) reduced the conjecture to two cases. The doublecross case concerns cubic graphs admitting drawings with two crossings incident with a common graph face. Edwards et al. (2016) proved this case. The apex case concerns biconnected cubic apex graphs. Inoue et al. (2026) presented a computer-assisted proof of the apex case, which, if valid, completes the proof of the conjecture.

See also

Apex Graph, Doublecross Graph, Edge Coloring, Petersen Graph, Snark, Tutte Conjecture

Explore with Wolfram|Alpha

References

Edwards, K.; Sanders, D. P.; Seymour, P.; and Thomas, R. "Three-Edge-Colouring Doublecross Cubic Graphs." J. Combin. Th. Ser. B 119, 66-95, 2016. https://doi.org/10.1016/j.jctb.2015.12.006.Inoue, Y.; Kawarabayashi, K.; Matsuo, R.; Miyashita, A.; Mohar, B.; and Sonobe, T. "Three-Edge-Coloring Apex Cubic Graphs." 24 Aug 2026. https://arxiv.org/abs/2608.22870.Robertson, N.; Seymour, P. D.; and Thomas, R. "Tutte's Edge-Colouring Conjecture." J. Combin. Th. Ser. B 70, 166-183, 1997. https://doi.org/10.1006/jctb.1997.1752.Robertson, N.; Seymour, P. D.; and Thomas, R. "Excluded Minors in Cubic Graphs." J. Combin. Th. Ser. B 138, 219-285, 2019. https://doi.org/10.1016/j.jctb.2019.02.002.Tutte, W. T. "On the Algebraic Theory of Graph Colorings." J. Combin. Th. 1, 15-50, 1966.

Cite this as:

Weisstein, Eric W. "Tutte Three-Edge-Coloring Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TutteThree-Edge-ColoringConjecture.html

Subject classifications