Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem

DOI10.1007/978-3-642-25870-1_17zbMath1341.05083OpenAlexW2220915800MaRDI QIDQ3104775

Andrew R. A. McGrae, Michele Zito

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_17

zbMATH Keywords

empire colouring problemforests of paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Related Items (2)

The complexity of the empire colouring problem for linear forests ⋮ On the complexity of the selective graph coloring problem in some special classes of graphs

Cites Work

• Biplanar graphs: A survey
• Martingales on Trees and the Empire Chromatic Number of Random Trees
• Colouring Random Empire Trees
• Solution of Heawood's empire problem in the plane.
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• The Thickness of the Complete Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem