Generalizations of the four-color theorem The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four color theorem with a description of their status. 
(Motivated by a comment of rupeixu to a recent blog post on my blog presenting a question by Abby Thompson regarding a natural generalization of the 4CT.)
Related question:Generalizations of Planar Graphs   .
 A: There is a recent generalization to $k$-uniform hypergraphs that are
embeddable in $\mathbb{R}^d$ without edge intersections.
"For $k=d=2$ the problem specializes to graph planarity":

Carl Georg Heise, Konstantinos Panagiotou, Oleg Pikhurko, Anusch Taraz.
"Coloring $d$-embeddable $k$-uniform Hypergraphs."
Discrete & Computational Geometry (2014) 52:663-679.
(arXiv abs link.)

"We say that $H = (V, E)$ is a $k$-uniform hypergraph
if the vertex set $V$ is a finite set and the
edge set $E$ consists of $k$-element subsets of $V$."
A: There are also interesting weak forms of the 4CT where the challenge is of course to give a direct proof. An immediate consequence of the 4CT is that every planar graph has an independent set of size $n/4$, the best known result (without using 4CT) is $2n/9$ by Albertson (1976). It is very interesting to ask about fractional coloring number. Hilton, Rado, and Scott, introduced the notion of fractional coloring and proved "A (< 5)-colour theorem for planar graphs (1973)."
We say that a graph $G$ have a fractional coloring number $t$ $(\chi^*(G)=t)$ if we can assign the independent sets of $G$ nonnegative weights such that the sum of weights of independent sets containing any given vertex is at most 1 and the total sum of weight is $t$, and, moreover, $t$ is the smallest number with this property.
Two remarkable conjectures by Heckman and Thomas are:
Conjecture 1: Every subcubic triangle-free graphis fractionally 14/5-colorable.
Conjecture 2: Every subcubic triangle-free planar graph is fractionally 8/3-colorable.
(So conjecture 1 is a strengthening of a weakening of the 4CT.)
in 2013, Dvořák, Sereni, and Volec in the paper Subcubic triangle-free graphs have fractional chromatic number at most 14/5 proved Conjecture 1!
A: Each planar graph is 5-choosable (Thomassen, 1995).
A: One of the most important generalizations of the four color theorem is Hadwiger's conjecture. The Hadwiger conjecture asserts that a graph without a $K_{r+1}$ minor is $r$-colorable. There is a further generalization called the Weak Hadwiger Conjecture. 
It is known that the Hadwiger conjecture is false for graphs with infinite chromatic number (consider the disjoint union of $K_n$ where $n\in\mathbb{N}$), whereas the Weak Hadwiger conjecture is true for those graphs (see this paper).
An interesting question is whether the Weak Hadwiger conjecture implies the Hadwiger conjecture for finite graphs.
A: 6 colors for a Klein bottle, 7 for a torus.
How about higher dimensional manifolds?
A: Let $P$ be a $d$-dimensional polytope  with $n$ vertices. For every $2$-dimensional face $F$ triangulate $F$ by non crossing diagonals. So if $F$ has $k$ sides you add $(k-3)$ edges. It is known that the total number of edges you get , denoted by $f^{\bf +}_1(P)$ (including the original edges of the polytope) satisfies the inequality $$f_1^{\bf +}(P) \ge dn - {{d+1} \choose {2}}.$$ 
A polytope is called elementary if equality holds:
$$f_1^{\bf +}(P) = dn - {{d+1} \choose {2}}.$$ 
It is known that If $P$ is elementary so is its dual $P^*$.
We can consider the following classes of graphs:
1) $E_d$ = Graphs of elementary $d$-polytopes and all their subgraphs
2) $F_d$ = Graphs obtained by elementary $d$-polytopes by triangulating all 2 faces by non crossing diagonals, and all their subgraphs.
For $d=3$ both classes are the class of planar graphs. 
Conjecture (weak)  Graphs in $E_d$  are $(d+1)$-colorable.
Conjecture (strong)  Graphs in $F_d$  are $(d+1)$-colorable.
Remarks: We can start instead of polytopes by arbitrary polyhedral $(d-1)$-dimensional pseudomanifolds. But it is conjectured that with such extensions we will not get new elementary objects. 
A: The stronger generalization from the comment above.


*

*Assign a trianglenumber of $+1$ or $-1$ to each triangle of a maximal planar graph with $v$ vertices and make all $2^{2(v-2)}$ different variations.

*For every variation define the vertexnumbers by making the sum $\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of $0$, $1$ or $2$.
Conjecture 1: The number of different variations of vertexnumbers for $v-2$ vertices is equal to $3^{v-2}$ if the two missing vertices are adjacent. 
Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this $v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then $4$-colorable. 
The number of different variations of vertexnumbers for ALL vertices is more than  $3^{v-2}$ except if all vertices have even degree (the graph is then 3-vertex-colorable). 
Conjecture 2: The number of different variations of vertexnumbers for $v$ vertices is equal to $3^{v-2}$ if all vertices have even degree. 
Understanding conjecture 2 can help to better understand conjecture 1.
A: A theorem of Grotzsch from 1959 asserts that every planar graph not containing a triangle is 3-colorable. This was reproved by Thomassen in "A short list color proof of Grotzsch’s theorem", J. Combin. Theory B, vol 88 (2003), 189–192.
A: The coloring of higher dimensional ball packings. 
A ball packing is a collection of balls with disjoint interiors.  The tangency graph of a ball packing takes the balls as vertices and connect two vertices if and only if they are tangent.  Planar graphs are the tangency graphs of 2-dimensional disk packings.  So the following is a generalization of four-color theorem.

Question: what is the maximum chromatic number $\chi_d$ for the tangency graph of a ball packing in dimension $d$?

I believe that everyone can prove that $\chi_d\le\kappa_d+1$ where $\kappa_d$ is the kissing number.  The question was asked by Bagchi and Datta (2012) who gave the trivial lower bound $\chi_d\ge d+2$.
As far as I know, Maehara (2007) first attack the problem for dimension $3$.  His construction for lower bound uses Moser spindle.  It generalizes to higher dimensions and gives $\chi_d\ge d+3$.
The problem has also been asked on MO. One result is an answer of Cantwell.  It uses halved cubes.  It can be generalized to higher dimensions by a result of Liniail, Mishulam and Tarsi (1988) and gives $\chi_d\ge d+4$ for infinitely many $d$.
So the current status is: $d+4\le\chi_d\le\kappa_d+1$.  There is a large gap in between.

update: I just improve the lower bound by constructing a unit ball packing in dimension $q^3-q^2+q$ with chromatic number $q^3+1$ where $q$ is a prime power.  There are many other ball packings with high chromatic number, see this answer. The gap is still very large.
A: Consider a finite family of non-overlapping circles. We can ask what is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors? By Koebe’s circle packing theorem (see this recent post) this is precisely the four color theorem so the answer is 4.
This observation suggests various generalizations and variations. See this post for quite a few of them. If you insist on unit circles but drop the condition "non-overlapping" you get Nelson's famous question about the chromatic number of the plane. Here are two questions.

*

*Consider a finite family of  circles such that every point in the plane is included in at most two circles.  What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Ringel’s circle conjecture (see this paper by Jackson and Ringel) asserts that the number of colors is bounded. (There is an example that five colors are required.)


*Consider a finite family of  pseudocircles.  Here every pseudocircle is a closed simple path and two pseudocicles are either disjoint or hace two crossing points. Two pseudocircles are adjacent if the lens described by them does not contain any point from any other pseudocircle. What is the minimum number of colors needed to color the pseudocircles so that adjacent pseudocircles are colored with different colors? (In particular, is this number finite?)

A: Here are two:
Recall that the four colour theorem is equivalent to the statement that bridgeless cubic planar graphs are three-edge-colourable.
There is Tutte’s three-edge-colouring conjecture that every cubic bridgeless graph not containing the Petersen graph as a minor is 3-edge-colourable. This is a theorem now.
A (still open) generalization of this is Tutte’s 4-flow conjecture that every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.
Another is a conjecture of Seymour about $d$-regular planar (multi-)graphs. This says that every $d$-regular planar graph which satisfies the natural cut condition (for every odd-cardinality subset $X$ of the vertices there are at least $d$ edges between $X$ and the complement) is $d$-edge-colourable. This is still open in general but known for values of $d \leq 8$ (see here).
A: The chromatic polynomial of any planar graph has no real roots that are greater than or equal to four.
Note that the four color theorem says that 4 cannot be a root, and it's well known that the roots can't be real numbers greater than or equal to 5.
A: Kronheimer and Mrowka recently defined an instanton invariant of embedded trivalent graphs (webs) in $\mathbb{R}^3$. This can be regarded as (roughly) counting the number of representations of the fundamental group of the complement of the graph to $SO(3)$ such that the meridian of each edge is sent to an involution. They conjecture that for planar webs their invariant gives the number of Tait colorings (it's easy to see that a Tait coloring gives a representation of this sort to the Klein four group). They show this is true for Eulerian planar trivalent graphs among others. They show that their invariant is always non-zero, and hence this conjecture implies the four color theorem. They also give various refinements of this conjecture in this paper and a sequel. See also this blog-post.
A: An algebraic reformulation:
Given the table of two ternary numbers of order 1 with two figures:
21
12
We do the following operation:
We replace in one column each figure with the two other ones, in the two different ways to make the next tables of order 1+1=2.
We get then two tables with four ternary numbers of order 2 with 3 figures.
Operation on the 1st column:
011
101
022
202
Operation on the 2nd column:
202
220
101
110
We can continue for order n, and get then: n! tables with 2^n different ternary numbers each with n+1 figures.
Proving that each table of some order has always at least two ternary numbers in common with any other table of the same order is one more generalization of the FCT. Here the two tables have 101 and 202 in common. 
Add a 0 to the right of every number in every table to see the relation with the illustration below. 
Illustration of the operations above:

A: Closely related conjectures are the following: An acyclic colouring of a graph is a colouring of its vertices so that the subgraph spanned on union of every two colour classes is acyclic (a forest). Grunbaum conjectured in 1973 that every planar graph has acyclic colouring with five colours. This was proved by Borodin in 1976 who further conjectured that five colours always suffice with the additional condition that the union of every $k$ colour classes, $1 \le k \le 4$ induces a $(k-1)$-degenerate graph.
A: Consider a graph $\Gamma$ embedded on a surface $\Sigma$. Is there a finite-sheeted cover $\tilde{\Sigma}$ of $\Sigma$ so that the induced cover $\tilde{\Gamma}$ of $\Gamma$ is 4-colorable? We know that the cover of $\Gamma$ induced by the universal cover of $\Sigma$ is 4-colorable (as is any planar cover) by the 4-color theorem, so one way to describe the question is can one make the universal cover of $\Sigma$ have a 4-coloring of the induced graph which is invariant under a finite-index subgroup of the covering translations?
For any graph, one can always take a finite cover which is bipartite, and this can also be arranged by an induced cover of an embedding in a surface. So the point of the question is to deal with the given embedding. Maybe a more natural way to phrase the question is to color a map on a surface. I'm not sure if this question has been posed before, so I don't have any references.  
A: Let me mention here Thompson's three questions: 
Question 1: Suppose that $G$ is the graph of a simple $d$-polytope with $n$ vertices. Suppose also that $n$ is even (this is automatic if $d$ is odd). Can we always properly color the edges of $G$ with $d$ colors?
Question 2 : Let $G$ be a dual graph of a triangulation of the $(d-1)$-dimensional sphere. Suppose that $G$ has an even number of vertices.  Is $G$ $d$-edge colorable?
Question 3: Let $G$ be a dual graph of a triangulation of a $(d-1)$-dimensional manifold, $d \ge 4$. Suppose that $G$ has an even number of vertices.  Is $G$ $d$-edge colorable?
Questions 1 and 2 coincides (by Steinitz's theorem) for $d=3$ and are equivalent there to the 4CT. 
The starting point for these questions is  a beautiful generalization for the 4CT proposed by Branko Grunbaum: 
Grunbaum's conjecture: The dual graph of a triangulation of every two-dimensional manifold is alwayas 3-edge colorable. 
Grunbaum's conjecture was disproved in 2009 by Martin Kochol.
A: One generalization with a spectral graph theory flavor is the Colin de Verdière Conjecture, originating in

Colin de Verdière, Yves. "Sur un nouvel invariant des graphes et un critere de planarité." Journal of Combinatorial Theory, Series B 50, no. 1 (1990): 11-21. Journal link (English translation in this volume)

For a graph $G$ with $n$ vertices, consider an $n\times n$ symmetric matrix $M$ satisfying:

*

*For every $i\neq j$, $M_{ij} < 0$ if $\{i,j\}$ is an edge in $G$, and $M_{ij} = 0$ otherwise.

(This looks a bit like a generalization of the usual graph Laplacian matrix.)
The smallest eigenvalue of $M$ must (by Perron-Frobenius) have multiplicity equal to the number of connected components of $G$.  So what about the multiplicity of the second smallest eigenvalue?  Now this may depend on the choice of $M$, so let's consider its maximum over all such matrices $M$.
Since the diagonal of $M$ is unconstrained, we may assume that this second-smallest eigenvalue is $0$.  Then we're asking about the largest possible corank of such a matrix $M$.
Finally, require of $M$ a sort of nondegeneracy condition, called the Strong Arnold Property:

*

*Within the space of $n\times n$ real symmetric matrices, the submanifold comprising those that satisfy the bulleted condition above and that comprising those with the same rank as $M$ intersect transversally at $M$.

(A theorem of van der Holst, Lovász and Schrijver gives an equivalent algebraic condition: The only symmetric matrix $X$ with $MX=0$ that is zero on the diagonal and on the edges of $G$ is $X=0$.)
The largest corank of a matrix $M$ satisfying both of the bulleted conditions above is the Colin de Verdière number of $G$, denoted $\mu(G)$.  This parameter has some nice properties, e.g., it is monotonic with respect to graph minors.
Most remarkably, Colin de Verdière showed that $\mu(G) \le 3$ if and only if $G$ is planar (and that $\mu(G) \le 2$ iff $G$ is outerplanar) and put forward

The Colin de Verdière Conjecture:   $\chi(G) \le \mu(G)+1$

Currently, the conjecture is known to hold for $\mu(G) \le 4$.  This relies on current proofs of the 4-color theorem, of course, although a direct proof of the conjecture could conceivably offer a very different route to that result.
ADDED:  Colin de Verdière showed $\mu(G)=n-1$ iff $G=K_n$.  (This seems obvious, but does require checking the Strong Arnold Property.)  Together with the minor-monotonicity mentioned above, this shows that the conjecture would follow as a special case of the Hadwiger Conjecture, as pointed out here in a comment by Gil Kalai.  This is also noted by Colin de Verdière himself upon stating the conjecture!
A: Another nice formulation is the following:
Prove that the vertices of a MPG (all faces are triangles) without crossing diagonals can be put on a integer unit grid, so that NO triangle has an integer area (= xx.5).
Example: An illustration for $K4$ 
Answer by P. Labarque
