What dictates whether a given planar map can be three-coloured? While reading about the four colour theorem, I've found some information that for many simple maps, three colours are in fact enough to provide the colouring. What constitues a "simpler" map, though? 
From what I've been able to google on the subject, it seems to be NP-complete to decide whether a given map can be three-coloured but maybe there are at least some giveaways about whether a given map is most likely possible to be three-coloured? Or some telltale signs that, while do not work for each and every map, provide a good approximation that a given map can, in fact, be three-coloured?
 A: It is indeed NP-complete to decide if a planar graph is $3$-colourable (see the paper "Some simplified NP-complete graph problems"). So it is unlikely we will ever see a nice characterization of planar $3$-colourable graphs. There are some known results however that give classes of planar $3$-colourable graphs. 
Outerplanar graphs (planar graphs where all vertices lie on the outerface) are known to be $3$-colourable. 
Series Parallel graphs (graphs not containing a $K_4$-minor) are known to be $3$-colourable. This is Hadwinger's conjecture (the $4$-colour theorem on steroids) applied to $K_{4}$-minors. 
Grotzech's theorem says that planar triangle free graphs are $3$-colourable. In general, if a graph contains no cycles of length $0 \bmod 3$ then the graph is $3$-colourable. There are a bunch of other generalizations of this result to get slightly wider sets of (planar) graphs.
Brook's theorem says that all sub-cubic (max degree $3$) graphs are $3$-colourable.
Graphs with degeneracy $2$ (all subgraphs have a vertex of degree $2$) are $3$-colourable.
Of course, if a graph has no odd cycles, then it is $2$-colourable, so bipartite planar graphs are $2$-colourable. 
