Colouring Graphs

[Jon Perry]

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?

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.

Jon Perry
perry at globalnet.co.uk
http://www.users.globalnet.co.uk/~perry/maths/
http://www.users.globalnet.co.uk/~perry/DIVMenu/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com