I’ve been quite busy writing up a survey of graph colouring algorithms. As an experiment, I’ve put up a draft of the manuscript on Bitbucket, including the source files.

The draft is available as a PDF document.
The sources can be inspected at the Bitbucket Git repository thusfeldt/graph-colouring-algorithms.

Even though the literature on graph colouring algorithms is vast, I was unable to find an earlier comprehensive survey. (In fact, the Wikipedia page Graph colouring, to which I have contributed quite a bit, is in pretty good shape.) Thus, I’ve found myself surveying results and techniques that are somewhat outside of my comfort zone, and made editorial choices about issues where I speak with little authority.

Thus, by making this draft available, I strongly invite comments of all kinds. Errors, miscalculations, sources of confusion, misunderstandings, criminal omissions of results or tacit assumptions, undue weight: Please tell me. Here or via email. If you’re really cool, use the issue tracker or fork the git repository, edit your change, and send me a pull request. (I dream of a distant future where all papers can be crowd-sourced and the original author just juggles diffs. I also dream of rolling pavements and flying cars, of course.)

I would especially like to hear comments from mathematicians and other researchers outside of theoretical computer science (what tacit assumptions have I forgotten to make explicit?), algorithms students at the beginning graduate level (is it understandable?), and graph colouring researchers (what favourite result of yours did I misunderstand or omit?).