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