Abstract
dc:description.abstractThis thesis deals with problems concerning the local properties of graphs with large chromatic number in hereditary classes of graphs. We construct intersection graphs of axis-aligned boxes and of lines in \mathbb{R}3 that have arbitrarily large girth and chromatic number. We also prove that the maximum chromatic number of a circle graph with clique number at most ω is equal to \Theta(ω \log ω). Lastly, extending the $\chi$-boundedness of circle graphs, we prove a conjecture of Geelen that every proper vertex-minor-closed class of graphs is $\chi$-bounded.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Davies, James
- Advisor dc:contributor.advisor
-
- Geelen, Jim
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/18679