There are many conjectured generalizations of the The Four Color Theorem. This is not a comprehensive survey, but rather a short pointer to as-yet unpublished results that people often ask about.

Tutte's edge 3-coloring conjecture

This is now a theorem:

THEOREM. Every 2-connected 3-regular graph with no minor isomorphic to the Petersen graph is edge 3-colorable.

A proof has been announced by N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas. The proof will be published in the following papers:
 

  • N. Robertson, P.D. Seymour and R.Thomas, Tutte's edge-colouring conjecture, J. Combin. Theory Ser. B. 70 (1997), 166-183.
  • N. Robertson, P.D. Seymour and R.Thomas, Cyclically 5-connected cubic graphs, arXiv:1503.02298.
  • N. Robertson, P.D. Seymour and R.Thomas, Excluded minors in cubic graphs, arXiv:1403.2118.
  • D. P. Sanders, P. D. Seymour and  R.Thomas, Edge 3-coloring cubic apex graphs, in preparation.
  • K. Edwards, D. P. Sanders, P.D. Seymour and  R.Thomas, Edge 3-coloring cubic doublecross graphs, arXiv:1411.4352.
  • These papers (except the fourth) are available from my homepage.

    Uniquely colorable planar graphs

    My former student Tom Fowler and I proved a conjecture of Fiorini and Wilson, and Fisk about uniquely colorable planar graphs. Here is one version:

    THEOREM. A 3-regular planar graph has a unique edge 3-coloring if and only it can be obtained from the complete graph on four vertices by repeatedly replacing vertices by triangles.

    A proof is in Tom's PhD thesis.



    Copyright Robin Thomas