Graph Colouring via The Probabilistic Method

The term Probabilistic Method refers to the proof of deterministic statements using probabilistic tools. The method has been successfully applied to a number of problems in the field of graph colouring. We survey some of the results thereby obtained. The talk is intended to be accessible and short on details. We will first define graph colouring, and explain the type of graph colouring problems which tend to attract interest. We then explain the probabilistic tools which are used to solve them, and why we would expect the type of tools that are used to be effective for solving the types of problems typically studied.

Bruce Reed, McGill University, Canada

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube