Colouring Graphs

[Jim Nastos]

On Mon, 3 Feb 2003, Jon Perry wrote:

> By expanding the problem, I mean expanding the graph, then colouring it
> using normal methods, but how do we then return to the original
> edge-coloured graph.

  It's not necessary. Say G is the edge-coloured graph. Then we form G' by 
completing the M(c) sets, colour G' appropriately, and the can overlay 
that vertex-colouring of G' onto G, which you already have, and it becomes 
valid in the sense that you described earlier about v U M(c) all having 
different colour for each v and c.
  Since the vertex set does not change through the transformation, the 
colouring works for both.

Jim