Professor Luke Postle has been named the recipient of the 2021 Coxeter-James Prize for his work in the area of graph theory. Professor Postle will receive his award and present a prize lecture during the Canadian Mathematical Society (CMS) Winter Meeting in December 2021.
The Coxeter-James Prize was inaugurated in 1978 to recognize young mathematicians who have made outstanding contributions to mathematical research.
“Congratulations to Luke, who is most deserving of this prize from the Canadian Mathematical Society,” said Mark Giesbrecht, Dean of the University of Waterloo’s Faculty of Mathematics. “He has established himself as a leading researcher in graph theory and combinatorics, and has made ground-breaking progress on many famous conjectures in graph colouring.”
Some of the famous conjectures in graph colouring that Professor Postle has made advances in include Hadwiger’s Conjecture, the Goldberg-Seymour Conjecture, Reed’s Conjecture, and Jaeger’s Conjecture. His research has resulted in him publishing in top journals such as Journal of Combinatorial Theory B (JCTB), Combinatorica, and Journal of Graph Theory, and gave talks at conferences and universities around the world.
Professor Postle is a researcher in Waterloo's Department of Combinatorics and Optimization. Since joining Waterloo in 2014, he was awarded a Tier 2 Canada Research Chair and an Early Researcher Award from the government of Ontario.
“I am deeply honored to receive this prize from the Canadian Mathematical Society," said Professor Postle. "I am also excited at the opportunity to share my work with the larger mathematical community”.
Professor Postle has launched a new paradigm in graph colouring with his introduction of a new generalization of colouring. Namely, in 2015, he and his collaborator Zdenek Dvorak introduced correspondence colouring in an article published in JCTB, now referred to as DP-colouring by the community after their surnames.
Correspondence colouring is a generalization of list colouring. List colouring, itself a generalization of colouring, was first introduced by Erdos, Rubin and Taylor in the 1970s and is now the subject of over a thousand journal articles. In list colouring, each vertex has its own list from which it must be coloured. In correspondence colouring, they abstracted this by removing any `global’ notion of colour and rather only using a `local’ notion, individual to each vertex. Such a generalization can actually be used for inductive purposes to solve list colouring problems; specifically, they used the concept to solve a 15-year-old conjecture that planar graphs without four to eight cycles are three-list-colourable. Since then, their article has garnered 86 citations in three years according to Google Scholar, and indeed the article is listed on JCTB’s website as its most cited article published since January 2018.
Correspondence colouring has been used to solve open colouring problems and has been studied in its own right as a natural form of colouring. For example, correspondence colouring proved a key ingredient in Professor Postle’s research on Reed’s conjecture.