Abstract
dc:description.abstractIn 1998, Reed conjectured that for every graph $G$, \chi(G) \leq \lceil \frac{1}{2}(\Delta(G)+1+ω(G)) \rceil, and proved that there exists $\varepsilon > 0$ such that \chi(G) \leq \lceil (1 - \varepsilon)(\Delta(G)+1) + \varepsilon ω(G) \rceil for every graph $G$. Recently, much effort has been made to prove this result for increasingly large values of $\varepsilon$ in graphs with sufficiently large maximum degree. One of the main lemmas used in deriving these bounds states that graphs which are list-critical are sparse. This result generally follows by applying a sufficient condition for list colouring complete multipartite graphs with parts of bounded size, and until recently a theorem of Erd\H{o}s, Rubin and Taylor for list colouring complete multipartite graphs with parts of size at most two was used. The current bottleneck in bounding $\chi(G)$ for an improved value of $\varepsilon$ is the case of small clique number. We derive new density lemmas exploiting this case by showing that our graph is contained in a complete multipartite graph with many parts of size three. In order to list colour in this setting, we apply a theorem of Noel, West, Wu and Zhu, as well as our own unbalanced variant of this result.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kroeker, Matthew Eliot
- Advisor dc:contributor.advisor
-
- Postle, Luke
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/16178