Back to search

University of Waterloo

The Local Chromatic Number

Abstract

dc:description.abstract

A graph vertex colouring is called k-local if the number of colours used in the closed neighbourhood of each vertex is at most k. The local chromatic number of a graph is the smallest k for which the graph has a proper k-local colouring. So unlike the chromatic number which is the minimum total number of colours required in a proper colouring, the local chromatic number is minimum number of colours that must appear in the closed neighbourhood of some vertex in a proper colouring. In this thesis we will examine basic properties of the local chromatic number, and techniques used to determine or bound it. We will examine a theory that was sparked by Lovász's original proof of the Kneser conjecture, using topological tools to give lower bounds on the chromatic number, and see how it is applicable to give lower bounds on the local chromatic number as well. The local chromatic number lies between the fractional chromatic number and the chromatic number, and thus it is particularly interesting to study when the gap between these two parameters is large. We will examine the local chromatic number for specific classes of graphs, and give a slight generalization of a result by Simonyi and Tardos that gives an upper bound on the local chromatic number for a class of graphs called Schrijver graphs. Finally we will discuss open conjectures about the chromatic number and investigate versions adapted to the local chromatic number.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Osang, Georg Fritz

Rights

Language dc:language.iso
en

Identifiers

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

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
related terms
citation

Osang, Georg Fritz. The Local Chromatic Number. University of Waterloo, 2014. http://hdl.handle.net/10012/8188