Colouring Random Empire Trees

DOI10.1007/978-3-540-85238-4_42zbMath1173.05322OpenAlexW1558737914MaRDI QIDQ3599154

Andrew R. A. McGrae, Michele Zito

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_42

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items

The complexity of the empire colouring problem for linear forests, The complexity of the empire colouring problem, Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• The four-colour theorem
• A short solution of Heawood's empire problem in the plane
• Random planar graphs
• Solution of Heawood's empire problem in the plane.
• Every planar map is four colorable
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• Enumeration of spanning trees of certain graphs
• Another Enumeration of Trees
• The two possible values of the chromatic number of a random graph