List-colourings of near-outerplanar graphs
A list-colouring of a graph is an assignment of a colour to each vertex v from its own list L(v) of colours. Instead of colouring vertices we may want to colour other elements of a graph such as edges, faces, or any combination of vertices, edges and faces. In this thesis we will study several of th...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2007
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/11157/ |
| _version_ | 1848791207344340992 |
|---|---|
| author | Hetherington, Timothy J. |
| author_facet | Hetherington, Timothy J. |
| author_sort | Hetherington, Timothy J. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | A list-colouring of a graph is an assignment of a colour to each vertex v from its own list L(v) of colours. Instead of colouring vertices we may want to colour other elements of a graph such as edges, faces, or any combination of vertices, edges and faces. In this thesis we will study several of these different types of list-colouring, each for the class of a near-outerplanar graphs. Since a graph is outerplanar if it is both K4-minor-free and K2,3-minor-free, then by a near-outerplanar graph we mean a graph that is either K4-minor-free or K2,3-minor-free.
Chapter 1 gives an introduction to the area of graph colourings, and includes a review of several results and conjectures in this area. In particular, four important and interesting conjectures in graph theory are the List-Edge-Colouring Conjecture (LECC), the List-Total-Colouring Conjecture (LTCC), the Entire Colouring Conjecture (ECC), and the List-Square-Colouring Conjecture (LSCC), each of which will be discussed in Chapter 1. In Chapter 2 we include a proof of the LECC and LTCC for all near-outerplanar graphs. In Chapter 3 we will study the list-colouring of a near-outerplanar graph in which vertices and faces, edges and faces, or vertices, edges and face are to be coloured. The results for the case when all elements are to be coloured will prove the ECC for all near-outerplanar graphs. In Chapter 4 we will study the list-colouring of the square of a K4-minor-free graph, and in Chapter 5 we will study the list-colouring of the square of a K2,3-minor-free graph. In Chapter 5 we include a proof of the LSCC for all K2,3-minor-free graphs with maximum degree at least six. |
| first_indexed | 2025-11-14T18:24:50Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-11157 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:24:50Z |
| publishDate | 2007 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-111572025-02-28T11:11:38Z https://eprints.nottingham.ac.uk/11157/ List-colourings of near-outerplanar graphs Hetherington, Timothy J. A list-colouring of a graph is an assignment of a colour to each vertex v from its own list L(v) of colours. Instead of colouring vertices we may want to colour other elements of a graph such as edges, faces, or any combination of vertices, edges and faces. In this thesis we will study several of these different types of list-colouring, each for the class of a near-outerplanar graphs. Since a graph is outerplanar if it is both K4-minor-free and K2,3-minor-free, then by a near-outerplanar graph we mean a graph that is either K4-minor-free or K2,3-minor-free. Chapter 1 gives an introduction to the area of graph colourings, and includes a review of several results and conjectures in this area. In particular, four important and interesting conjectures in graph theory are the List-Edge-Colouring Conjecture (LECC), the List-Total-Colouring Conjecture (LTCC), the Entire Colouring Conjecture (ECC), and the List-Square-Colouring Conjecture (LSCC), each of which will be discussed in Chapter 1. In Chapter 2 we include a proof of the LECC and LTCC for all near-outerplanar graphs. In Chapter 3 we will study the list-colouring of a near-outerplanar graph in which vertices and faces, edges and faces, or vertices, edges and face are to be coloured. The results for the case when all elements are to be coloured will prove the ECC for all near-outerplanar graphs. In Chapter 4 we will study the list-colouring of the square of a K4-minor-free graph, and in Chapter 5 we will study the list-colouring of the square of a K2,3-minor-free graph. In Chapter 5 we include a proof of the LSCC for all K2,3-minor-free graphs with maximum degree at least six. 2007-07-12 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/11157/1/thesis.pdf Hetherington, Timothy J. (2007) List-colourings of near-outerplanar graphs. PhD thesis, University of Nottingham. Choosability minor-free graph edge colouring total colouring list-square colouring simultaneous colouring |
| spellingShingle | Choosability minor-free graph edge colouring total colouring list-square colouring simultaneous colouring Hetherington, Timothy J. List-colourings of near-outerplanar graphs |
| title | List-colourings of near-outerplanar graphs |
| title_full | List-colourings of near-outerplanar graphs |
| title_fullStr | List-colourings of near-outerplanar graphs |
| title_full_unstemmed | List-colourings of near-outerplanar graphs |
| title_short | List-colourings of near-outerplanar graphs |
| title_sort | list-colourings of near-outerplanar graphs |
| topic | Choosability minor-free graph edge colouring total colouring list-square colouring simultaneous colouring |
| url | https://eprints.nottingham.ac.uk/11157/ |