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
Tutte's edge 3-coloring conjecture
This is now a theorem:
THEOREM. Every 2-connected 3-regular graph with no minor
to the Petersen graph is edge 3-colorable.
A proof has been announced by N.
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
J. Combin. Theory Ser. B. 70 (1997), 166-183.
N. Robertson, P.D. Seymour and R.Thomas, Cyclically 5-connected cubic
N. Robertson, P.D. Seymour and R.Thomas, Excluded minors in cubic
D. P. Sanders, P. D. Seymour and R.Thomas, Edge 3-coloring cubic apex graphs, in
K. Edwards, D. P. Sanders, P.D. Seymour and R.Thomas, Edge 3-coloring cubic
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
THEOREM. A 3-regular planar graph has a unique edge
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.