Martingales on Trees and the Empire Chromatic Number of Random Trees

摘要

We study the empire colouring problem (as defined by Percy Heawood in 1890) for maps whose dual planar graph is a tree, with empires formed by exactly r countries. We prove that, for each fixed r > 1, with probability approaching one as the size of the graph grows to infinity, the minimum number of colours for which a feasible solution exists takes one of seven possible values.