Topics in Graph Colouring
PhD Thesis. Link available soon.
We study two variants of graph (vertex) colourings: multi-colouring and correspondence colouring.
More specifically, the following topics are studied.
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?
3. 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?
4. How different graph operations affect the correspondence chromatic number of multigraphs?
For definitions and results, see the original thesis.
Multi-Colouring of Graphs: towards Stahl’s Conjecture
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.
For given n, k, if a graph is (n,k)-colourable, then for what n', k' is the whole graph (n',k')-colourable?
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.
Joint work with Jan van den Heuvel. Research talks on this project has been given at BCC 2022, ICGT 2022 and Shandong University Qi Lu Forum.
For definitions and results, see Chapter 2 of the above thesis.
n-Colourable Induced Subgraphs
In 2000, Albertson, Grossman, and Haas asked the following question: given a graph G with list chromatic number n, if each vertex has been assigned a list with n' colours, 1 ≤ n' ≤ n, can we always properly colour at least n'|V(G)|/n vertices of G?
We study the partial colouring problem associated with other variants of graph colouring and answer the following negatively with a series of examples: for any fractional-r-colourable graph G and s < r, does it always have a fractional-s-colourable subgraph of at least r|V(G)|/s vertices? Similar properties are also observed on multiple colouring. Then we study the following.
(a) Given a rational number r > 0 and integer n ≥ 1, for what real number a can we guarantee that every fractional-r-colourable graph G has an n-colourable induced subgraph with at least a|V(G)| vertices?
(b) Given rational numbers r, s > 0, for what real number b can we guarantee that every fractional-r-colourable graph G has a fractional-s-colourable induced subgraph with at least b|V(G)| vertices?
Joint work with Jan van den Heuvel. Research talks on this project has been given at BCC 2021.
For definitions and results, see Chapter 3 of the above thesis.
Partial Multi-Colouring and Fractional Colouring
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?
This question is inspired by a partial colouring conjecture asked by Albertson, Grossman, and Haas 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'.
Joint work with Jan van den Heuvel. Research talks on this project has been given at BCC 2021.
For definitions and results, see Chapter 4 of the above thesis.
Partial 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.
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.
For definitions and results, see Chapter 6 of the above thesis.
The Effect of Graph Operations on Correspondence Colouring
As a variant of vertex colouring of graphs, correspondence colouring generalises ordinary and list colouring. Whilst multiple edges do not provide additional restrictions in ordinary or list colouring, additional constraints in correspondence colouring appear when multiple edges are present. We study how certain graph operations affect the correspondence chromatic number of multigraphs and present an interesting result that adding one edge can increase the correspondence chromatic number by arbitrarily large.
Joint work with Jan van den Heuvel. Research talks on this project has been given at LSE, Shandong University and BYMAT 2020.
For detailed definitions and results, see Chapter 5 of the above thesis.
Counting Independent Sets in Graphs
We study an algorithm introduced by Kleitman and Winston. This algorithm encodes independent sets of a given graph in an invertible manner, which allows us to bound number of independent sets in graphs. In particular, we study its applications on counting sum-free sets, counting independent sets in certain types of graphs, counting C4-free graphs with fixed vertex set and proving Roth’s theorem.
This is a final-year (of the 4-year Msci programme) project at UCL. The project was completed under the supervision of Dr John Talbot.
