Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$48,000.00

Graph Colouring and Local Algorithms

FY 2022-23

Summary
Local Algorithms for Graph Colouring The main areas of this proposed research program are two-fold: 1) to develop local algorithms for some of the most important problems in graph colouring, and 2) to develop local versions of the most prominent graph colouring theorems wherein the parameters (e.g. degree, colours) are local to the vertices. 1. Algorithms and Local Algorithms for Colouring Graphs Finding efficient polynomial-time algorithms for colouring graphs is a fundamental problem, both for its theoretical implications and practical heuristics. Graph colouring is a useful model for many applications in information and communication technologies such as server processing, frequency allocation, scheduling and distributed algorithms. While substantial progress has been made in recent decades on improved bounds for the number of colours needed in these problems, there are still many recent important results that lack algorithms. Moreover, even those problems that have admitted algorithms lack efficient local algorithms, which are essential for use in distributed computing. Objectives. 1.1 Develop Local Algorithms for Colouring Graphs on Surfaces. 1.2 Develop Algorithms for Potential Method. 1.3 Develop Local Algorithms for Colouring Graphs with given Clique Number. Broader Impact. The proposed research develops local algorithms for some of the most important graphs colourings problems in a variety of areas from planar graphs and sparse graphs to graphs of given clique number. The research uses newly developed techniques like hyperbolic families and correspondence colourings to develop a theory of local graph colouring algorithms and will have a major impact on both of those fields. 2. Local Versions of Colouring Theorems We further propose developing local versions of the results themselves. Creating local versions is a new paradigm for graph colouring that I have taken a leading role in [CCV J5, J13]. Such versions are both far-reaching generalizations of previous results while simultaneously holding much potential for applications. Since most graph colouring results bound the number of colours needed in terms of parameters of a graph, a local version of a graph colouring result then is one where the parameters (including number of colours) are localized to the vertices. Objectives. 2.1 Develop Better Bounds for Reed's Conjecture and its Local Version. 2.2 Develop Local Versions for Edge Colouring Results. 2.3 Develop Local Versions for k-uniform Hypergraph Colouring Results. Broader Impact. The proposed research develops local versions for many of the most fundamental graph colouring results. Furthermore, it spearheads an entirely new area of graph colouring which strongly generalizes the most important known results while shifting the underlying paradigm of graph colouring itself toward the local parameters of networks - a very useful development both for practical applications and in the development of local algorithms.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2019-04304
Name nom
Postle, Luke
Department département
Combinatorics and Optimization - Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2019
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:4
Partie
1
Nb partie
5
Application title
Graph Colouring and Local Algorithms
Application summary
Local Algorithms for Graph Colouring The main areas of this proposed research program are two-fold: 1) to develop local algorithms for some of the most important problems in graph colouring, and 2) to develop local versions of the most prominent graph colouring theorems wherein the parameters (e.g. degree, colours) are local to the vertices. 1. Algorithms and Local Algorithms for Colouring Graphs Finding efficient polynomial-time algorithms for colouring graphs is a fundamental problem, both for its theoretical implications and practical heuristics. Graph colouring is a useful model for many applications in information and communication technologies such as server processing, frequency allocation, scheduling and distributed algorithms. While substantial progress has been made in recent decades on improved bounds for the number of colours needed in these problems, there are still many recent important results that lack algorithms. Moreover, even those problems that have admitted algorithms lack efficient local algorithms, which are essential for use in distributed computing. Objectives. 1.1 Develop Local Algorithms for Colouring Graphs on Surfaces. 1.2 Develop Algorithms for Potential Method. 1.3 Develop Local Algorithms for Colouring Graphs with given Clique Number. Broader Impact. The proposed research develops local algorithms for some of the most important graphs colourings problems in a variety of areas from planar graphs and sparse graphs to graphs of given clique number. The research uses newly developed techniques like hyperbolic families and correspondence colourings to develop a theory of local graph colouring algorithms and will have a major impact on both of those fields. 2. Local Versions of Colouring Theorems We further propose developing local versions of the results themselves. Creating local versions is a new paradigm for graph colouring that I have taken a leading role in [CCV J5, J13]. Such versions are both far-reaching generalizations of previous results while simultaneously holding much potential for applications. Since most graph colouring results bound the number of colours needed in terms of parameters of a graph, a local version of a graph colouring result then is one where the parameters (including number of colours) are localized to the vertices. Objectives. 2.1 Develop Better Bounds for Reed's Conjecture and its Local Version. 2.2 Develop Local Versions for Edge Colouring Results. 2.3 Develop Local Versions for k-uniform Hypergraph Colouring Results. Broader Impact. The proposed research develops local versions for many of the most fundamental graph colouring results. Furthermore, it spearheads an entirely new area of graph colouring which strongly generalizes the most important known results while shifting the underlying paradigm of graph colouring itself toward the local parameters of networks - a very useful development both for practical applications and in the development of local algorithms.
University of Waterloo - $48,000 Grant (2022-23) | Canada Spends