An algorithmic framework for colouring locally sparse graphs

Ewan Davies, Ross J. Kang, François Pirot +1

We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fix…