Graph Colouring and Frequency Assignment
In this thesis we study some graph colouring problems which arise from mathematical models of frequency assignment in radiocommunications networks, in particular from models formulated by Hale and by Tesman in the 1980s. The main body of the thesis is divided into four chapters. Chapter 2 is the sh...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2005
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/10135/ |
| _version_ | 1848791037871390720 |
|---|---|
| author | Waters, Robert James |
| author_facet | Waters, Robert James |
| author_sort | Waters, Robert James |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | In this thesis we study some graph colouring problems which arise from mathematical models of frequency assignment in radiocommunications networks, in particular from models formulated by Hale and by Tesman in the 1980s.
The main body of the thesis is divided into four chapters. Chapter 2 is the shortest, and is largely self-contained; it contains some early work on the frequency assignment problem, in which each edge of a graph is assigned a positive integer weight, and an assignment of integer colours to the vertices is sought in which the colours of adjacent vertices differ by at least the weight of the edge joining them.
The remaining three chapters focus on problems which combine frequency assignment with list colouring, in which each vertex has a list of integers from which its colour must be chosen. In Chapter 3 we study list colourings where the colours of adjacent vertices must differ by at least a fixed integer s, and in Chapter 4 we add the additional restriction that the lists must be sets of consecutive integers. In both cases we investigate the required size of the lists so that a colouring can always be found.
By considering the behaviour of these parameters as s tends to infinity, we formulate continuous analogues of the two problems, considering lists which are real intervals in Chapter 4, and arbitrary closed real sets in Chapter 5. This gives rise to two new graph invariants, the consecutive choosability ratio tau(G) and the choosability ratio sigma(G). We relate these to other known graph invariants, provide general bounds on their values, and determine specific values for various classes of graphs. |
| first_indexed | 2025-11-14T18:22:09Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-10135 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:22:09Z |
| publishDate | 2005 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-101352025-02-28T11:07:14Z https://eprints.nottingham.ac.uk/10135/ Graph Colouring and Frequency Assignment Waters, Robert James In this thesis we study some graph colouring problems which arise from mathematical models of frequency assignment in radiocommunications networks, in particular from models formulated by Hale and by Tesman in the 1980s. The main body of the thesis is divided into four chapters. Chapter 2 is the shortest, and is largely self-contained; it contains some early work on the frequency assignment problem, in which each edge of a graph is assigned a positive integer weight, and an assignment of integer colours to the vertices is sought in which the colours of adjacent vertices differ by at least the weight of the edge joining them. The remaining three chapters focus on problems which combine frequency assignment with list colouring, in which each vertex has a list of integers from which its colour must be chosen. In Chapter 3 we study list colourings where the colours of adjacent vertices must differ by at least a fixed integer s, and in Chapter 4 we add the additional restriction that the lists must be sets of consecutive integers. In both cases we investigate the required size of the lists so that a colouring can always be found. By considering the behaviour of these parameters as s tends to infinity, we formulate continuous analogues of the two problems, considering lists which are real intervals in Chapter 4, and arbitrary closed real sets in Chapter 5. This gives rise to two new graph invariants, the consecutive choosability ratio tau(G) and the choosability ratio sigma(G). We relate these to other known graph invariants, provide general bounds on their values, and determine specific values for various classes of graphs. 2005 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/10135/1/waters-thesis.pdf Waters, Robert James (2005) Graph Colouring and Frequency Assignment. PhD thesis, University of Nottingham. graph theory graph colouring graph coloring combinatorics frequency assignment |
| spellingShingle | graph theory graph colouring graph coloring combinatorics frequency assignment Waters, Robert James Graph Colouring and Frequency Assignment |
| title | Graph Colouring and Frequency Assignment |
| title_full | Graph Colouring and Frequency Assignment |
| title_fullStr | Graph Colouring and Frequency Assignment |
| title_full_unstemmed | Graph Colouring and Frequency Assignment |
| title_short | Graph Colouring and Frequency Assignment |
| title_sort | graph colouring and frequency assignment |
| topic | graph theory graph colouring graph coloring combinatorics frequency assignment |
| url | https://eprints.nottingham.ac.uk/10135/ |