Colouring Random Empire Trees

DOI10.1007/978-3-540-85238-4_42MaRDI QIDQ3599154zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Martingales on Trees and the Empire Chromatic Number of Random Trees
• The complexity of the empire colouring problem
• Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
• scientific article; zbMATH DE number 3935072
• The complexity of the empire colouring problem for linear forests

Cites work

• A short solution of Heawood's empire problem in the plane
• Another Enumeration of Trees
• Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon
• Enumeration of spanning trees of certain graphs
• Every planar map is four colorable
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1196612 (Why is no real title available?)
• scientific article; zbMATH DE number 1146225 (Why is no real title available?)
• scientific article; zbMATH DE number 2038777 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• On the complexity of H-coloring
• Random planar graphs
• Solution of Heawood's empire problem in the plane.
• The four-colour theorem
• The two possible values of the chromatic number of a random graph

Cited in

(5)

• Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
• Complexity results for the empire problem in collection of stars
• Martingales on Trees and the Empire Chromatic Number of Random Trees
• The complexity of the empire colouring problem for linear forests
• The complexity of the empire colouring problem

This page was built for publication: Colouring Random Empire Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3599154)