# Bruce Reed (mathematician)

Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, a former Canada Research Chair in Graph Theory at McGill University. His research is primarily in graph theory. He is a distinguished research fellow of the Institute of Mathematics in the Academia Sinica, Taiwan, and an adjunct professor at the University of Victoria in Canada.

## 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.
In 2021 he left McGill, and subsequently became a researcher at the Academia Sinica and an adjunct professor at the University of Victoria.

## 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, random satisfiability problems, acyclic coloring, tree decomposition, and constructive versions of the Lovász local lemma.
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.

## Selected publications
### Articles

| AMR91. | Alon, Noga; McDiarmid, Colin; Reed, Bruce (1991), "Acyclic coloring of graphs", Random Structures & Algorithms, 2 (3): 277–288, doi:10.1002/rsa.3240020303, MR 1109695. |
| CR92. | Chvátal, V.; Reed, B. (1992), "Mick gets some (the odds are on his side)", Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 620–627, doi:10.1109/SFCS.1992.267789, ISBN 978-0-8186-2900-6, S2CID 5575389. |
| R92. | Reed, Bruce A. (1992), "Finding approximate separators and computing tree width quickly", Proc. 24th Annual ACM Symposium on Theory of computing, pp. 221–228, doi:10.1145/129712.129734, ISBN 978-0897915113, S2CID 16259988. |
| MR95. | Molloy, Michael; Reed, Bruce (1995), "A critical point for random graphs with a given degree sequence", Random Structures & Algorithms, 6 (2–3): 161–179, doi:10.1002/rsa.3240060204, MR 1370952. |
| R97. | Reed, B. A. (1997), "Tree width and tangles: a new connectivity measure and some applications", Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge: Cambridge Univ. Press, pp. 87–162, doi:10.1017/CBO9780511662119.006, ISBN 9780511662119, MR 1477746. |
| MR98a. | Molloy, Michael; Reed, Bruce (1998), "The size of the giant component of a random graph with a given degree sequence", Combinatorics, Probability and Computing, 7 (3): 295–305, doi:10.1017/S0963548398003526 (inactive 8 March 2025), hdl:1807/9487, MR 1664335, S2CID 3712019{{citation}}: CS1 maint: DOI inactive as of March 2025 (link). |
| MR98b. | Molloy, Michael; Reed, Bruce (1998), "Further algorithmic aspects of the local lemma", Proc. 30th Annual ACM Symposium on Theory of computing, pp. 524–529, doi:10.1145/276698.276866, hdl:1807/9484, ISBN 978-0897919623, S2CID 9446727. |
| RS02. | Reed, Bruce; Sudakov, Benny (2002), "List colouring of graphs with at most (2 − o(1))χ vertices", Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), Higher Ed. Press, Beijing, pp. 587–603, arXiv:math/0304467, Bibcode:2003math......4467R, MR 1957563. |

### Books

| MR02. | Molloy, Michael; Reed, Bruce (2002), Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, vol. 23, Berlin: Springer-Verlag, ISBN 978-3-540-42139-9. |