Colouring Graphs

[Jim Nastos]

On Sun, 2 Feb 2003, Jon Perry wrote:

> Given a vertex V, let M(c) be the set of vertices adjacent to V along an
> edge of colour c.
> 
> Each vertex in M(c) must be a different colour to V.

  Once again, this is an unsatisfactory definition. Every vertex adjacent 
to V is going to be in an M(c) set for some c. So by your definition, for 
any V every neighbout of V must have a different colour.
  Did you instead mean that every vertex in an M(c) set must have 
a different colour from V as well from one another?
  If this is the case, then for your edge-coloured graph G we just have to 
take each vertex and complete the sets of vertices forming your M(c) sets. 
(to complete means to add an edge between every pair of vertices in the 
set.) In which case it is not a very interesting colouring.
  Again, if I'm misunderstanding your definition, please be more careful 
in your definition.

Jim