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 ... -
Uniqueness and Complexity in Generalised Colouring
Farrugia, Alastair (University of Waterloo, 2003)The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition ... -
Software Architecture Recovery based on Pattern Matching
Sartipi, Kamran (University of Waterloo, 2003)Pattern matching approaches in reverse engineering aim to incorporate domain knowledge and system documentation in the software architecture extraction process, hence provide a user/tool collaborative environment for ...