Improper colourings of graphsReport as inadecuate

Improper colourings of graphs - Download this document for free, or read online. Document in PDF available to download.

Reference: Ross J. Kang, (2008). Improper colourings of graphs. DPhil. University of Oxford.Citable link to this page:


Improper colourings of graphs

Abstract: We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings.The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood.Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and large unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.

Digital Origin:Born digital Type of Award:DPhil Level of Award:Doctoral Awarding Institution: University of Oxford


Prof Colin J. H. McDiarmidMore by this contributor


 Bibliographic Details

Issue Date: 2008

Copyright Date: 2008 Identifiers

Urn: uuid:a93d8303-0eeb-4d01-9b77-364113b81a63 Item Description

Type: thesis;

Language: en Keywords: graph colouring probabilistic combinatorics random graphs unit disk graphs telecommunications improper colouring acyclic colouring frugal colouringSubjects: Combinatorics Computer science (mathematics) Discrete mathematics (statistics) Tiny URL: ora:2015


Author: Dr Ross J. Kang - institutionUniversity of Oxford facultyMathematical,Physical and Life Sci



Related documents