Colouring Graphs

[Jim Nastos]

On Sun, 2 Feb 2003, Jon Perry wrote:

Jon:

> 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) U V} must be a different colour.

Me:

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

Jon:

> Not sure that I follow...

  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). In this 
new graph with all the extra edges, we are just required to colour 
the vertices of the graph in the standard graph colouring way - that is, 
colour the vertices such that no two neighbours have the same colour. This 
new graph no longer has any coloured edges that your original graph has, 
and a valid colouring of the new graph becomes a valid "Jon"-colouring of 
the original graph, and hence I claim that it is not that interesting a 
colouring scheme to consider.

Jim