Graph Three Colouring

Subscribe!

My latest posts can be found here:
Previous blog posts:

What is Graph Three-Colouring?

Here is something you may have seen before. Take a map, any map, and colour the regions so that if two regions share a border, they must get different colours.

Usually we count the exterior as a region and everything still holds. Some people use the convenience of drawing a box and saying that they don't care about anything outside it. Either is a choice, and it doesn't make much difference.

So if we have only one region then clearly we colour it with whatever colour we choose, and we only need one colour. If we have two regions then they are going to touch somewhere, so they will have to get different colours. Fair enough.

If we have a checkerboard sort of arrangement then we still only need two colours, colouring them in the usual way. The black squares only meet at a corner, and that's OK - they are not sharing a boundary, so they don't need to be different colours. We can choose to make them different, but that's different.

If you see what I mean.

So by creating bigger and bigger checkerboards we can make maps of whatever size we like that can still be covered by just two colours. We say that we can create "arbitrarily large" two-colourable maps.

If all of that seems easy and obvious, here's an extra challenge. Suppose we also have to colour the outside, bounding region. The checkerboard pattern always has both colours on the squares on the boundary, so we can't use one of those two colours for the outside. That means that if we have to colour the outside as well, the idea of larger and larger checkerboards no longer lets us create arbitrarily large two-colourable maps, because the exterior has to get a third colour.

Moving beyond the checkerboard ...

In fact, we can be more daring and more adventurous. We don't have to have anything as simple as a tiling of the plane with squares. Take any doodle made with a single pen stroke, and ending up where it started. The resulting diagram can always be coloured with just two colours.

This is what we'll call The Doodle Theorem, and we'll come back to that in a little while.

But sometimes things require three colours, a simple pie in three pieces is an example. Indeed, if you decide that the exterior also requires colouring, a pie into any number of pieces greater than one requires at least three colours, and sometimes four.

But one day back in the 1800s, De Morgan wrote:

 "A student of mine [Guthrie] asked me to day to give him a reason for a fact which I did not know was a fact - and do not yet. He says that if a figure be any how divided and the compartments differently colored so that figures with any portion of common boundary line are differently colored - four colors may be wanted but not more - the following is his case in which four colors are wanted. Query cannot a necessity for five or more be invented ..."

And thus was born the Four Colour Conjecture.

But I'm not going to go into that here! There are many good papers and books explaining the history, etc. Instead, I'm off in a different direction.

Leaving the plane behind

Why are we doing this? What's wrong with talking about colouring maps?

When we colour the regions on a map we are specifically limited to working on (or in) the two-dimensional surface. But when we are talking about graphs we are no longer limited to a surface. We can talk about graphs in abstract.

So let's return, as promised, to what we call The Doodle Theorem. We claim that a map drawn with a single pen stroke that returns to its starting point can be two-coloured. A proof goes roughly like this:

• Take a planar graph that's been drawn with a single pen stroke that returns to its starting point.

• Such a graph is said to have an "Euler Cycle".

• At every vertex we go in, and then out, so

• Every vertex must have an even number of edges.

• In the dual, a circuit around a vertex of the original will have an even number of edges,

• ... because each edge in the dual crosses an edge in the original.

• Extend that, and we can show that every circuit has an even number of edges.

• Note: This requires a bit of proof!

• A graph is bipartite if and only if every circuit is even.

• This also requires a bit of proof.

None of that is obvious! That's why this has the status of a theorem, and you can read more about it here: The Doodle Theorem.

So the dual is bipartite, and that means it can be bi-coloured! So the dual can be bi-coloured, and that corresponds to a bi-colouring of the original map.

And we're done - a planar graph with an Euler Cycle can be bi-coloured.

Bi-Partite graphs

 A map and its dual
It's pretty clear that a bi-partite graph can be two coloured, but if you're given a graph, how easy or hard is it to decide if it's bi-partite?

Easy. Really easy.

To decide if a graph is bi-partite, pick one vertex, colour it red. Colour its neighbours green, colour their neighbours red, and just keep going. If the graph is bi-partite this never goes wrong. If it goes wrong, it's not bipartite. And that's it!

But this map is not bi-colourable - the dual is not bi-partite. So given a graph it's really easy to tell if it's bi-partite or not, is the same true of tri-partite-ness?

Given a graph, can we easily tell if it's tri-partite?

No.

What?

 Here we are talking about colouring the vertices - we have now left behind the idea of colouring regions in maps - that's too limiting, because it's restricted to graphs/maps that can be drawn in the plane (or other two-dimensional surface).
Well, to be tri-partite is the same as being three-colourable, because a three-colouring gives us a division of the vertices into three sets where the edges are only ever between the sets, never within. So to ask if a graph is tri-partite is to ask if it is three colourable.

And it turns out that this is thought to be hard. You may notice that I say "thought to be". The thing is - no one knows if it really is hard. What currently is known is this:

• We don't know of any algorithm that can efficiently determine if a graph is three-colourable.

Of course, we need to define what we mean by "efficient," but we can do that. What's more, this is a question that is worth a million dollars. Literally. It's one of the Millennium Problems to determine if there is, or if there is not, an efficient algorithm for solving the three-colouring problem.

To get a deeper understanding of this, we can look at Factoring Via Graph Three Colouring. There we can see, explicitly, that a problem thought to be hard can in fact be solved, provide we can three-colour efficiently. But here's a flavour.

Three-colouring a graph

 Given a graph, an independent set is a set of vertices that have no edges between them.
We can three-colour a graph if we can find an independent set of vertices such that the remaining graph is bi-partite. Given an independent set it's trivial (as shown above) to decide if the remaining graph forms a bipartite graph, so it comes down to finding independent sets. And given a set, it's trivial to decide if it's independent. So we can find any possible three-colourings by

• Find a subset of vertices, then
• if it's independent,
• if the remainder is bipartite,
• you've found a three-colouring.

But if you have $N$ vertices in your graph, there are $2^N$ possible subsets, so this algorithm is terribly inefficient.

Problem is, every algorithm we know is inefficient - there is no known algorithm that takes time that is polynomial in the number of vertices.

 <<<< Prev <<<< The Doodle Theorem : >>>> Next >>>> When Obvious Is Not Obvious ...

I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate.

If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely.