Colouring Graphs

[Jim Nastos]

On Sat, 1 Feb 2003, Jon Perry wrote:

> If we have a graph with the edges coloured with no rules, what colouring are
> allowed for the vertices such that if n vertices have the same coloured edge
> in common, then they must be coloured differently?

  Are you saying: (1) If M = set of all vertices which have an m-coloured 
edge adjacent to them, all all vertices in M must be coloured differently. 
Or (2) If M = set of all vertices on *one* specific coloured edge, then 
all vertices in M must be coloured differently. ?
  If (1) then I don't see how your first example satisfies this because 
every vertex in the graph is adjacent to both r & b edges. If (2), then M 
is always of size 2 and this reduces to the common notion of vertex 
colouring.
  Please be more formal in what you are trying to say... define your sets 
and terms.

  Jim

> e.g. consider the square with alternate edge colourings. Then 2 colours are
> sufficient:
> 
> G--r--W
> |     |
> |     |
> b     b
> |     |
> |     |
> W--r--G
> 
> However, with 2 adjecent edges the same colour, we need 3:
> 
> G--r--Y
> |     |
> |     |
> r     b
> |     |
> |     |
> W--b--G
> 
> Lower case indicates the colour of an edge.