Topics in graph colouring

Xu, Xinyi (2023) Topics in graph colouring. PhD thesis, London School of Economics and Political Science.

Text - Submitted Version Download (2MB)

Abstract

In this thesis, we study two variants of graph (vertex) colourings: multicolouring and correspondence colouring. In ordinary graph colouring, each vertex receives a colour. Such a colouring is proper if adjacent vertices receive different colours. In k-multi-colouring, each vertex receives a set of k colours, and such a multi-colouring is proper if adjacent vertices receive disjoint set of colours. A graph is (n, k)-colourable if there is a proper k-multi-colouring of it using n colours. In the first part of the thesis, we study the following two questions. 1. For given n, k and n′, k′, if a graph is (n, k)-colourable, then what is the largest subgraph of it that is (n′, k′)-colourable? 2. For given n, k, if a graph is (n, k)-colourable, then for what n′, k′ is the whole graph (n′, k′)-colourable? Question 1 is inspired by a partial colouring conjecture asked by Albertson, Grossman, and Haas [2] in 2000 regarding list colouring. We obtain exact answers for specific values of the parameters, and upper and lower bounds on the largest (n′, k′)-colourable subgraph for general values of n′, k′. For Question 2, we first observe how it can be reformulated into a conjecture by Stahl from 1976 regarding Kneser graphs, and prove new results towards Stahl’s conjecture. In the second part of the thesis, we study another variant of colouring, which is known as correspondence colouring. In correspondence colouring, each vertex is associated with a prespecified list of colours, and there is prespecified correspondence associated with each edge specifying which pair of colours from the two endvertices correspond. (On each edge, a colour on one endvertex corresponds to at most one colour on the other endvertex.) A correspondence colouring is proper if each vertex receives a colour from its prespecified list, and that for each edge, the colours on its endvertices do not correspond. A graph is n-correspondence-colourable if a proper correspondence colouring exist for any prespecified correspondences on any prespecified n-colour-lists associated to each vertex. As correspondence colouring is a generalisation of list colouring, it is natural to ask whether Albertson, Grossman, and Haas’ conjecture can be generalised to correspondence colouring. Unfortunately, there are graphs on which their conjectured value does not hold, and we will present a series of them. We then study: for given n and n′, how many vertices of a n-correspondence colourable graph can always be properly correspondence-coloured with arbitrary correspondences and arbitrary n′-colour-lists on that graph? We generalise some results from the original conjecture in list colouring. Then we discuss some sufficient conditions for a proper correspondence colouring to exist. The correspondence chromatic number of a graph is the smallest n such that the graph is n-correspondence colourable. We study how different graph operations affect the correspondence chromatic number of multigraphs, in which multiple edges are allowed.

Item Type:	Thesis (PhD)
Additional Information:	© 2023 Xinyi Xu
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	Van Den Heuvel, Jan
URI:	http://etheses.lse.ac.uk/id/eprint/4554

Actions (login required)

Record administration - authorised staff only