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.

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005611