Luke Postle


Canada Research Chair in Graph Theory

Tier 2 - 2015-07-01
Renewed: 2020-05-01
University of Waterloo
Natural Sciences and Engineering Research Council

519-888-4567, ext. 33601
lpostle@uwaterloo.ca

Research involves

Studying the structural, topological and chromatic properties of graphs.

Research relevance

This research will to lead to new algorithmic and computational tools to help explain various phenomena that happen in transportation, communication and social networks.

Research summary

Graph colouring is one of the most important and storied subfields of graph theory. Graph colouring consists of partitioning the nodes in a network into pairwise non-adjacent sets called colours. Dr. Postle’s research plan is to develop local versions of the most important graph colouring results where local means that the number of colours available at a node only depends on local parameters. This research will generalize in a far-reaching way the previous results in the area while having more promise for future applications. In addition, Postle will develop distributed efficient algorithms to find such colourings.