Martingales on Trees and the Empire Chromatic Number of Random Trees
Colin Cooper, Andrew R. A. McGrae and Michele Zito
Abstract
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.