McGrae, ARA and Zito, M
(2014)
The Complexity of the Empire Colouring Problem.
Algorithmica, 68 (2).
pp. 483-503.
Text
revised.pdf - Author Accepted Manuscript Download (902kB) |
Abstract
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: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3005611 |