List-colourings of near-outerplanar graphs

Hetherington, Timothy J. (2007) List-colourings of near-outerplanar graphs. PhD thesis, University of Nottingham.

[img]
Preview
PDF
1793Kb

Abstract

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.

Item Type:Thesis (PhD)
Supervisors:Woodall, D.R.
Uncontrolled Keywords:Choosability, minor-free graph, edge colouring, total colouring, list-square colouring, simultaneous colouring
Faculties/Schools:UK Campuses > Faculty of Science > School of Mathematical Sciences
ID Code:1157
Deposited By:Dr Timothy Hetherington
Deposited On:03 Mar 2010 17:34
Last Modified:03 Mar 2010 17:34

Archive Staff Only: item control page