The complexity of the empire colouring problem

DOI10.1007/S00453-012-9680-0MaRDI QIDQ476435zbMATHOpenAlexFDO

Authors Andrew R. A. McGrae, Michele Zito

Publication date 2 December 2014

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.2162

zbMATH Keywords

colouringgraph algorithmsNP-hardnessplanar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $sgeq3$, the problem is NP-hard even if the graph is a forest of paths of arbitrary lengths (for any $rgeq2$, 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 $rgeq2$, if $3leqsleq2r-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 $rgeq3$. 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 $rgeq3$.

Recommendations

• Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
• The complexity of the empire colouring problem for linear forests
• Complexity results for the empire problem in collection of stars
• Colouring Random Empire Trees
• Martingales on Trees and the Empire Chromatic Number of Random Trees

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 3195968 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Biplanar graphs: A survey
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• Colouring Random Empire Trees
• Cycle decompositions of complete graphs
• Graph theory
• Introduction to algorithms.
• Martingales on Trees and the Empire Chromatic Number of Random Trees
• Reducibility among combinatorial problems
• Remarks on the thickness and outerthickness of a graph
• Solution of Heawood's empire problem in the plane.
• The Thickness of the Complete Graph
• The thickness of graphs: A survey

Cited in

(7)

• Complexity results for the empire problem in collection of stars
• Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
• The complexity of the empire colouring problem for linear forests
• The 1-Color Problem and the Brylawski Model
• Thickness and colorability of geometric graphs
• Martingales on Trees and the Empire Chromatic Number of Random Trees
• Colouring Random Empire Trees

This page was built for publication: The complexity of the empire colouring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476435)