Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
From MaRDI portal
Publication:3104775
DOI10.1007/978-3-642-25870-1_17zbMath1341.05083MaRDI 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
05C38: Paths and cycles
05C10: Planar graphs; geometric and topological aspects of graph theory
05C15: Coloring of graphs and hypergraphs
05C12: Distance in graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C07: Vertex degrees
Related Items
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