Back to search

University of Waterloo

Acyclic Colouring of Graphs on Surfaces

Abstract

dc:description.abstract

An acyclic k-colouring of a graph G is a proper k-colouring of G with no bichromatic cycles. In 1979, Borodin proved that planar graphs are acyclically 5-colourable, an analog of the Four Colour Theorem. Kawarabayashi and Mohar proved in 2010 that "locally" planar graphs are acyclically 7-colourable, an analog of Thomassen's result that "locally" planar graphs are 5-colourable. We say that a graph G is critical for (acyclic) k-colouring if G is not (acyclically) k-colourable, but all proper subgraphs of G are. In 1997, Thomassen proved that for every k >= 5 and every surface S, there are only finitely many graphs that embed in S that are critical for k-colouring. Here we prove the analogous result that for each k >= 12 and each surface S, there are finitely many graphs embeddable on S that are critical for acyclic k-colouring. This result implies that there exists a linear time algorithm that, given a surface S and large enough k, decides whether a graph embedded in S is acyclically k-colourable.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Redlin, Shayla
Advisor dc:contributor.advisor
  • Postle, Luke

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

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

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

Redlin, Shayla. Acyclic Colouring of Graphs on Surfaces. University of Waterloo, 2018. http://hdl.handle.net/10012/13732