The Complexity of the Empire Colouring Problem

McGrae, ARA and Zito, M
(2014) The Complexity of the Empire Colouring Problem. Algorithmica, 68 (2). pp. 483-503.

[img] Text
revised.pdf - Author Accepted Manuscript

Download (902kB)


We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in Q. J. Pure Appl. Math. 24:332–338, 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−2r+14−−−−−√+32). 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≥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.

Item Type: Article
Additional Information: ## TULIP Type: Articles/Papers (Journal) ##
Uncontrolled Keywords: colouring, planar graphs, NP-hardness, algorithms
Depositing User: Symplectic Admin
Date Deposited: 09 Feb 2017 16:38
Last Modified: 19 Jan 2023 07:19
DOI: 10.1007/s00453-012-9680-0
Related URLs: