Facial Nonrepetitive Graph Colourings

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Rioux-Maldague, Lucas

Date: 

2015

Abstract: 

A facial path is a path of consecutive vertices on the boundary walk of a face of a plane graph G. A nonrepetitive facial colouring of G is a vertex colouring such that the sequence of colours of any facial path is nonrepetitive, and the minimum number of colours required for such a colouring is the facial Thue chromatic number of G.

Using a new blocking set technique, we show that the facial Thue chromatic number of an outerplane graph is bounded by 11, and by 7 for outerplane graphs that contain at most one 2-connected component.

Furthermore, we show that the facial Thue chromatic number of plane graphs is bounded by twice the facial Thue chromatic number of outerplane graphs, which results in an upper bound of 22 for this parameter, an improvement over the previous bound of 24 by Barat and Czap (Journal of Graph Theory, 2013).

Subject: 

Computer Science
Mathematics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Computer Science: 
M.C.S.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).