Cereceda, Luis (2007) Mixing graph colourings. PhD thesis, The London School of Economics and Political Science (LSE).

PDF
 Submitted Version
Download (579kB)  Preview 
Abstract
This thesis investigates some problems related to graph colouring, or, more precisely, graph recolouring. Informally, the basic question addressed can be phrased as follows. Suppose one is given a graph G whose vertices can be properly kcoloured, for some k ≥ 2. Is it possible to transform any kcolouring of G into any other by recolouring vertices of G one at a time, making sure a proper kcolouring of G is always maintained? If the answer is in the affirmative, G is said to be kmixing. The related problem of deciding whether, given two kcolourings of G, it is possible to transform one into the other by recolouring vertices one at a time, always maintaining a proper kcolouring of G, is also considered. These questions can be considered as having a bearing on certain mathematical and ‘realworld’ problems. In particular, being able to recolour any colouring of a given graph to any other colouring is a necessary prerequisite for the method of sampling colourings known as Glauber dynamics. The results presented in this thesis may also find application in the context of frequency reassignment: given that the problem of assigning radio frequencies in a wireless communications network is often modelled as a graph colouring problem, the task of reassigning frequencies in such a network can be thought of as a graph recolouring problem. Throughout the thesis, the emphasis is on the algorithmic aspects and the computational complexity of the questions described above. In other words, how easily, in terms of computational resources used, can they be answered? Strong results are obtained for the k = 3 case of the first question, where a characterisation theorem for 3mixing graphs is given. For the second question, a dichotomy theorem for the complexity of the problem is proved: the problem is solvable in polynomial time for k ≤ 3 and PSPACEcomplete for k ≥ 4. In addition, the possible length of a shortest sequence of recolourings between two colourings is investigated, and an interesting connection between the tractability of the problem and its underlying structure is established. Some variants of the above problems are also explored.
Item Type:  Thesis (PhD) 

Additional Information:  © 2007 Luis Cereceda 
Library of Congress subject classification:  Q Science > QA Mathematics 
Sets:  Departments > Mathematics Collections > LSE History of Thought theses 
Supervisor:  van den Heuvel, Jan 
URI:  http://etheses.lse.ac.uk/id/eprint/131 
Actions (login required)
Record administration  authorised staff only 