Acyclic Colouring of Graphs on Surfaces
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.
Collections
Cite this version of the work
Shayla Redlin
(2018).
Acyclic Colouring of Graphs on Surfaces. UWSpace.
http://hdl.handle.net/10012/13732
Other formats
Related items
Showing items related by title, author, creator and subject.
-
Simultaneous Graph Representation Problems
Jampani, Krishnam Raju (University of Waterloo, 2011-02-18)Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves ... -
Mining Butterflies in Streaming Graphs
Sheshbolouki, Aida (University of Waterloo, 2023-07-12)This thesis introduces two main-memory systems sGrapp and sGradd for performing the fundamental analytic tasks of biclique counting and concept drift detection over a streaming graph. A data-driven heuristic is used to ... -
On Geometric Drawings of Graphs
Arroyo Guevara, Alan Marcelo (University of Waterloo, 2018-04-18)This thesis is about geometric drawings of graphs and their topological generalizations. First, we study pseudolinear drawings of graphs in the plane. A pseudolinear drawing is one in which every edge can be extended ...