University of Waterloo
Correspondence Colouring and its Applications to List Colouring and Delay Colouring
Abstract
dc:description.abstractIn 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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Saleh, Rana
- Advisor dc:contributor.advisor
-
- Haxell, Penny
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/17563