Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem

摘要

We study the empire colouring problem (as defined by Percy Heawood in 1890) for maps containing empires formed by exactly γ > 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/γ. However, if s ≥ 3, the problem is NP-hard for forests of paths of arbitrary lengths (if s < γ) for trees (if γ ≥ 2 and s < 2γ) and arbitrary planar graphs (if s < 7 for γ = 2, and s < 6γ - 3, for γ ≥ 3). The result for trees shows a perfect dichotomy (the problem is NP-hard if 3 ≤ s ≤ 2γ - 1 and polynomial time solvable otherwise). The one for planar graphs proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than 6γ - 3 colours graphs of thickness γ ≥ 3.