Graph Three Colouring

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Subscribe!
@ColinTheMathmo

My latest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:

What is Graph Three-Colouring?

http://www.solipsys.co.uk/images/Map.png
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.

http://www.solipsys.co.uk/images/Checkerboard.png
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.

http://www.solipsys.co.uk/images/ThreeColourPie.png
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.

Abstracting away from the map ...

http://www.solipsys.co.uk/images/Doodle1a.png
A map, with
watch-towers
http://www.solipsys.co.uk/images/Doodle2a.png
We mark the
capitals
http://www.solipsys.co.uk/images/Doodle3a.png
... and join them
with roads
http://www.solipsys.co.uk/images/Doodle4a.png
The dual graph
Let's look at our map. We are thinking, of course, of the regions as countries, and the lines as borders between them. We then have watchtowers wherever the borders meet, and sometimes on the border as well. So we have regions, lines, and points. To use the technical terms from graph theory, we have faces (although they are still sometimes called regions), edges, and vertices.

So our map is a graph that can be drawn on the plane - it is a planar graph.

Now let's do the following. Think of the regions as countries, and mark on our map each of the capitals. If two countries share a border, mark in a road joining the capitals. Don't put any other roads, and don't have the roads cross each other. In this way we have a new diagram of vertices (the capitals) and edges (the roads).

We're also going to say that if a particular border has a watchtower in the middle, or even more than one watchtower along its length, we will put a road for each section of boundary. So two capitals may have more than one road joining them.

This seems to be a useful idea, and we give it a name. Here we can see a map, then we overlay onto it the capitals and the roads joining them, and finally we erase the original map and get left with just the road network. This final diagram is called the dual of the original.

If we can assign colours to the capitals (the vertices) such that each road (edge) has a different colour at each end, then the countries can inherit the capital's colour, and that gives us a colouring of the original map. But in the same way, a valid colouring of the regions induces a colouring of the capitals in such a way that any two capitals (vertices) that are joined by a road (edge) must have different colours.

So colouring the original map is exactly the same task as colouring the vertices in the dual.

"So what?" - you may think.

http://www.solipsys.co.uk/images/Doodle5a.png
Colour the
capitals
http://www.solipsys.co.uk/images/Doodle6a.png
Induced colouring
of the map
From Doodle
to dual
to colouring

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:

http://www.solipsys.co.uk/images/DoodleExample.png

  • 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

http://www.solipsys.co.uk/images/Map_n_Dual.png
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?

What about tri-partite?

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


You should follow me on twitter @ColinTheMathmo

Comments

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.


Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!