Back to search

University of Waterloo

Sparsity in Critical Graphs with Small Clique Number

Abstract

dc:description.abstract

In 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 × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/16178

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kroeker, Matthew Eliot. Sparsity in Critical Graphs with Small Clique Number. University of Waterloo, 2020. http://hdl.handle.net/10012/16178