Colouring Graphs

[Jim Nastos]

On Mon, 3 Feb 2003, Jon Perry wrote:

> '  To ensure that every pair of vertices in M(c) have a different colour,
> we can just add an edge between every pair of vertices in M(c).'
> 
> We can't just DO this. Once we have a graph, we assigned 'random' colours to
> each edge, and then we must colour the vertices, following the rule that in
> {M(c) U V} all vertices must be coloured differently.

  You can "DO" this just as much as you can "DO" your own colouring. Yes, 
the edges are randomly coloured, but given such a graph with randomly 
coloured edges and asking such a question as you have, we can transform 
the problem easily into a standard vertex-colouring problem on an 
easy-to-describe normal graph (normal in that it is just vertices and 
edges and no specified colours on anything.)

Jim