The complexity of the empire colouring problem

DOI10.1007/s00453-012-9680-0zbMath1318.68095arXiv1109.2162OpenAlexW3103087101MaRDI QIDQ476435

Michele Zito, Andrew R. A. McGrae

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

colouringplanar graphsgraph algorithmsNP-hardness

Mathematics Subject Classification ID

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

Related Items (1)

Thickness and colorability of geometric graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Remarks on the thickness and outerthickness of a graph
• The thickness of graphs: A survey
• 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
• Reducibility among Combinatorial Problems
• The Thickness of the Complete Graph

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