The Complexity of the Empire Colouring Problem
We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in Q.J. Pure Appl. Math. 24:332338, 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?3, the problem is NP-hard even if the graph is a for forests of paths of arbitrary lengths (for any r?2, provided \(s < 2r - \sqrt{2r + \frac{1}{4}}+ \frac{3}{2}\)). Furthermore we obtain a complete characterization of the problems 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?2, if 3?s?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?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?3.
colouring np-hardness planar graphs algorithms