Graph Colouring, Part Four

re: Graph Colouring, Part Four

Rick C — Thu, 29 Jul 2010 15:35:45 GMT

Ha!

Ok, thanks. Wasn't trying to cause trouble, just wondering if I had missed something of significance.

re: Graph Colouring, Part Four

Rick C — Wed, 28 Jul 2010 18:59:16 GMT

Maybe I missed something but is there any significance to the fact that you draw your graphs such that sometimes you have multiple lines leading out from a single point and sometimes not? Consider Chile which has 3 lines leading out from two points. Does that mean anything?

It means that I am (1) not very good at using PowerPoint, and (2) too lazy to install Visio. - Eric

re: Graph Colouring, Part Four

Peter M — Tue, 27 Jul 2010 02:36:41 GMT

...and the commenting software ate the leading spaces in my awful ascii diagrams. I should really know better.

re: Graph Colouring, Part Four

Peter M — Tue, 27 Jul 2010 02:34:17 GMT

Everyone makes the "map requiring 7 colours" on the torus look so complicated and ugly, but it isn't really.

Start with a hexagonal tiling of the plane (pardon what follows...each "*" is a tile but it should really be in a monospaced font):

* * * * * * *

* * * * * * * *

* * * * * * *

* * * * * * * *

Now number the tiles in each row from 0 to 6, but stagger each row differently. Each "0" tile in each row should be two and a half tiles to the right of a "0" tile in the row below it:

5 6 0 1 2 3 4

0 1 2 3 4 5 6 0

3 4 5 6 0 1 2

5 6 0 1 2 3 4 5

Now (this is the part where ascii fails me) draw a parallelogram with vertices in the centre of four tiles marked "0" (such as the four leftmost "0" tiles in the diagram above), and identify opposite edges as before. There's your map. If you want your torus to be constructed from a square instead of a parallelogram you can apply an affine transformation.

re: Graph Colouring, Part Four

Erik — Mon, 26 Jul 2010 19:34:04 GMT

Eric - thanks. I mis-read your original statement - hence the confusion. =)

re: Graph Colouring, Part Four

RossM — Mon, 26 Jul 2010 17:54:00 GMT

If you didn't want to write the backtracking algorithm yourself, you could also solve this problem using Microsoft Solver Foundation:

var context = SolverContext.GetContext();

var model = context.CreateModel();

var domain = Domain.IntegerRange(1, 4);

Decision Brazil = new Decision(domain, "Brazil");

Decision FrenchGuinea = new Decision(domain, "FrenchGuinea");

Decision Suriname = new Decision(domain, "Suriname");

Decision Guyana = new Decision(domain, "Guyana");

Decision Venezuela = new Decision(domain, "Venezuela");

Decision Colombia = new Decision(domain, "Colombia");

Decision Ecuador = new Decision(domain, "Ecuador");

Decision Peru = new Decision(domain, "Peru");

Decision Chile = new Decision(domain, "Chile");

Decision Bolivia = new Decision(domain, "Bolivia");

Decision Paraguay = new Decision(domain, "Paraguay");

Decision Uruguay = new Decision(domain, "Uruguay");

Decision Argentina = new Decision(domain, "Argentina");

model.AddDecisions(Brazil, FrenchGuinea, Suriname, Guyana, Venezuela, Colombia, Ecuador, Peru, Chile, Bolivia, Paraguay, Uruguay, Argentina);

model.AddConstraints("neighbors",

Brazil != FrenchGuinea, Brazil != Suriname, Brazil != Guyana, Brazil != Venezuela, Brazil != Colombia, Brazil != Peru, Brazil != Bolivia,

Brazil != Paraguay, Brazil != Uruguay, Brazil != Argentina, FrenchGuinea != Suriname, Suriname != Guyana, Guyana != Venezuela,

Venezuela != Colombia, Colombia != Ecuador, Ecuador != Peru, Peru != Bolivia, Peru != Chile, Chile != Bolivia, Chile != Argentina,

Bolivia != Paraguay, Bolivia != Argentina, Paraguay != Argentina, Argentina != Uruguay);

var solution = context.Solve();

Console.Out.Write(solution.GetReport());

re: Graph Colouring, Part Four

Erik — Mon, 26 Jul 2010 17:25:24 GMT

How could a fully connected subset of size n require more than n colors? That doesn't seem to make sense.

I didn't say that a fully connected subset of size n ever requires more than n colours. I said "if any graph has a fully connected subset of size n then the graph requires at least n colours (and perhaps more)" which is a completely different statement than your statement.

For example, consider the graph A--B--C--D--E--back to A. That graph has five fully connected subgraphs of size two: {A, B}, {B, C}, {C, D}, {D, E} and {E, A}. It has no fully connected subgraphs of any size larger than two. We therefore know that it requires at least two colours; in fact, it requires three. Knowing the size of the largest clique only gives us a lower bound; the topology of the rest of the graph is also relevant. - Eric

re: Graph Colouring, Part Four

nick — Mon, 26 Jul 2010 15:31:31 GMT

"Let's call a subset of a graph where every node in the subset is connected to every other node in the subset a "fully connected subset"

Is that not just a clique?

Yes. - Eric