The Complexity of the Empire Colouring Problem

Details The Complexity of the Empire Colouring Problem The Complexity of the Empire Colouring Problem

2011-09-09

arxiv.org/abs/1109.2162v1

Computer Science

Computational Complexity

23 pages, 12 figures

Scientific paper

We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in 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 \geq 3$, the problem is NP-hard even if the graph is a forest of paths of arbitrary lengths (for any $r \geq 2$, provided $s < 2r - \sqrt{2r + 1/4+ 3/2). 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 \geq 2$, if $3 \leq s \leq 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 \geq 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 \geq 3$.

Affiliated with

Also associated with

No associations

Rating

The Complexity of the Empire Colouring Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of the Empire Colouring Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of the Empire Colouring Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-38251