This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.
|Title of host publication||Topics in Chromatic Graph Theory|
|Editors||Lowell W. Beineke, Robin J. Wilson|
|Publisher||Cambridge University Press|
|Publication date||May 2015|
|Publication status||Published - May 2015|
|Series||Encyclopedia of Mathematics and Its Applications|