The complexity of the empire colouring problem

DOI10.1007/S00453-012-9680-0zbMATH Open1318.68095arXiv1109.2162OpenAlexW3103087101MaRDI QIDQ476435FDOQ476435

Authors: Andrew R. A. McGrae, Michele Zito 

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

• Graph theory
• Introduction to algorithms.
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cycle decompositions of complete graphs
• Title not available (Why is that?)
• Solution of Heawood's empire problem in the plane.
• Martingales on Trees and the Empire Chromatic Number of Random Trees
• Colouring Random Empire Trees
• The thickness of graphs: A survey
• Biplanar graphs: A survey
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• The Thickness of the Complete Graph
• Title not available (Why is that?)
• Remarks on the thickness and outerthickness of a graph

Cited In (7)

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

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)