Back to search

University of Waterloo

Local properties of graphs with large chromatic number

Abstract

dc:description.abstract

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

Rights

Language dc:language.iso
en

Identifiers

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

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

Davies, James. Local properties of graphs with large chromatic number. University of Waterloo, 2022. http://hdl.handle.net/10012/18679