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, J. Combin. Theory Ser. B 125 (2017), 132-167, 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,
Three-edge-colouring doublecross cubic graphs,
J. Combin. Theory Ser. B 119 (2016), 66--95,
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