Blog - Title

# July, 2010

• #### Graph Colouring, Part Five

I said last time that I was interested in finding colourings for graphs that have lots of fully connected subgraphs, aka "cliques". For instance, I'd like to find a four-colouring for this sixteen-node graph: Yuck. What a mess. What this graph...
• #### Graph Colouring, Part Four

Let's give it a try. Can we colour South America with only four colours? Let's start by stating what all the edges are in the graph of South America: const int Brazil = 0; const int FrenchGuiana = 1; const int Suriname = 2; const int Guyana = 3;...
• #### Graph Colouring with Simple Backtracking, Part Three

OK, we've got our basic data structures in place. Graph colouring is a very well-studied problem. It's known to be NP-complete for arbitrary graphs, so (assuming that P!=NP) we're not going to find an always-fast algorithm for colouring an arbitrary...
• #### Graph Colouring With Simple Backtracking, Part Two

Before I begin a quick note: congratulations and best wishes to David Johnson, currently the president of my alma mater, the University of Waterloo. The Queen has appointed him to be the next Governor General of Canada come this October. For those of...