Correspondence Colouring and its Applications to List Colouring and Delay Colouring
Abstract
In this thesis, we study correspondence colouring and its applications to list colouring
and delay colouring. We give a detailed exposition of the paper of Dvořák, and Postle
introducing correspondence colouring.
Moreover, we generalize two important results in delay colouring. The first is a result
by Georgakopoulos, stating that cubic graphs are 4-delay colourable. We show that delay
colouring can be formulated as an instance of correspondence colouring. Then we show that
the modified line graph of a cubic bipartite graph is generally 4-correspondence colourable,
using a Brooks’ type theorem for correspondence colouring. This allows us to give a more
simple proof of a stronger result. The second result is one by Edwards and Kennedy, which
states that quartic bipartite graphs are 5-delay colourable. We introduce the notion of p-cyclic correspondence colouring which is a type of correspondence colouring that generalizes
delay colouring. We then prove that the modified line graph of a quartic bipartite graph
is 5-cyclic correspondence colourable using the Combinatorial Nullstellensatz.
We also show that the maximum DP-chromatic number of any cycle plus triangles (CPT)
graph is 4. We construct a CPT graph with DP-chromatic number at least 4. Moreover, the
upper bound follows easily from the Brooks’ type theorem for correspondence colouring.
Finally, we do a preliminary investigation into using parity techniques in correspondence
colouring to prove that CPT graphs are 3-choosable.
Collections
Cite this version of the work
Rana Saleh
(2021).
Correspondence Colouring and its Applications to List Colouring and Delay Colouring. UWSpace.
http://hdl.handle.net/10012/17563
Other formats
Related items
Showing items related by title, author, creator and subject.
-
Canadian Literatures Beyond the Colour Line: Re-Reading the Category of South-Asian Canadian Literature
Lobb, Diana Frances (University of Waterloo, 2011-03-18)This dissertation examines current academic approaches to reading South Asian-Canadian literature as a multicultural “other” to Canadian national literature and proposes an alternative reading strategy that allows for these ... -
Computerized and Non-Computerized Colour Vision Tests
Almustanyir, Ali (University of Waterloo, 2014-08-05)Introduction: Measuring colour discrimination of people who carry out tasks where colour is used to convey information and accurate colour judgments are essential for safe and efficient performance of the task is important ... -
Characterizing Colour-Word Contingency Learning
Lin, Ying-Hsin (University of Waterloo, 2015-04-28)Contingencies are constantly found in everyday situations and humans are extraordinarily adept at learning them, whether implicitly or explicitly. The learning of contingencies can benefit behaviour in many ways, some ...