Tech Reports

ULCS-10-007

Colouring Empires in Random Trees (PhD Thesis)

Andrew McGrae

Abstract

In this thesis we study the empire colouring problem as defined by Percy Heawood in 1890 for maps whose dual planar representation is a tree and have empires formed from exactly r vertices. We define the reduced graph of one such tree as being the graph formed by replacing each empire in the tree by a single vertex such that an edge is present between two vertices u and v of the reduced graph if there was an edge in the original tree joining a vertex belonging to the empire corresponding to u to a vertex belonging to the empire corresponding to v. We then give several results on a number of structural properties of these graphs assuming that the underlying tree is a random labelled tree, and compare them to those of other types of random graphs with the same number of edges. The main contribution of this thesis is a set of results on the worst-case and average-case properties of the empire colourings of trees having an upper bound s on the number of distinct colours used. We first show that if each empire contains exactly r countries, the empire colouring problem can be solved using no more than 2r colours on maps whose dual planar graph is a tree. Furthermore we give an inductive method for building instances that require these many colours. Then, motivated by the results of an empirical investigation of a number of colouring heuristics, we study the proportion of trees on a given number of vertices for which the empire colouring problem can be solved with s leq 2r colours. We prove that for every fixed positive integer r there exists a very precise lower bound on s beneath which almost all trees will admit no r-empire s-colouring. For larger values of s we are then able to give constant positive lower bounds on the probability that s colours are sufficient to colour a random tree.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.