Thore Husfeldt

Draft survey about graph colouring algorithms

with 3 comments

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?).


Written by thorehusfeldt

June 18, 2013 at 13:52

Posted in Uncategorized

3 Responses

Subscribe to comments with RSS.

  1. The Bitbucket links are broken, but I found the new address of the repository at, for anybody wondering.


    October 7, 2013 at 11:19

  2. Very nice survey!
    Two links: here is an online bibliography on graph coloring at:
    and collection of results on well-known benchmarks at:

    Stefano Gualandi (@famo2spaghi)

    November 25, 2013 at 10:56

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: