  We investigate the computational complexity of the empire colouring problem
(as defined by Percy Heawood in 1890) for maps containing empires formed by
exactly $r > 1$ countries each. We prove that the problem can be solved in
polynomial time using $s$ colours on maps whose underlying adjacency graph has
no induced subgraph of average degree larger than $s/r$. However, if $s \geq
3$, the problem is NP-hard even if the graph is a forest of paths of arbitrary
lengths (for any $r \geq 2$, provided $s < 2r - \sqrt(2r + 1/4+ 3/2)$.
Furthermore we obtain a complete characterization of the problem's complexity
for the case when the input graph is a tree, whereas our result for arbitrary
planar graphs fall just short of a similar dichotomy. Specifically, we prove
that the empire colouring problem is NP-hard for trees, for any $r \geq 2$, if
$3 \leq s \leq 2r-1$ (and polynomial time solvable otherwise). For arbitrary
planar graphs we prove NP-hardness if $s<7$ for $r=2$, and $s < 6r-3$, for $r
\geq 3$. The result for planar graphs also proves the NP-hardness of colouring
with less than 7 colours graphs of thickness two and less than $6r-3$ colours
graphs of thickness $r \geq 3$.
