Name Bruce Reed Role Mathematician | ||
 | ||
Books Graph Colouring and the Probabilistic Method | ||
Bruce Alan Reed is a Canadian mathematician and computer scientist, the Canada Research Chair in Graph Theory and a professor of computer science at McGill University. His research is primarily in graph theory.
Contents
Academic career
Reed earned his Ph.D. in 1986 from McGill, under the supervision of Vašek Chvátal. Before returning to McGill as a Canada Research Chair, Reed held positions at the University of Waterloo, Carnegie Mellon University, and the French National Centre for Scientific Research.
Reed was elected as a fellow of the Royal Society of Canada in 2009, and is the recipient of the 2013 CRM-Fields-PIMS Prize.
Research
Reed's thesis research concerned perfect graphs. With Michael Molloy, he is the author of a book on graph coloring and the probabilistic method. Reed has also published highly cited papers on the giant component in random graphs with a given degree sequence,[MR95][MR98a] random satisfiability problems,[CR92] acyclic coloring,[AMR91] tree decomposition,[R92][R97] and constructive versions of the Lovász local lemma.[MR98b]
He was an invited speaker at the International Congress of Mathematicians in 2002. His talk there concerned a proof by Reed and Benny Sudakov, using the probabilistic method, of a conjecture by Kyoji Ohba that graphs whose number of vertices and chromatic number are (asymptotically) within a factor of two of each other have equal chromatic number and list chromatic number.[RS02]