Colouring Graphs

[Jim Nastos]

On Mon, 3 Feb 2003, Jon Perry wrote:

> Hmmm, a counter-example?
> 
> 1-r-2
> |   |
> r   r
> |   |
> 3-r-4
> |   |
> b   b
> |   |
> 2-b-1

  First of all, why not try what I've have stated as fact, that is, your 
valid vertex colouring above *Will always* work on the corresponding graph 
constructed/ (below) 

> However:
> 
> A o---o B
>   |\ /|
>   | / |
>   |/ \|
> C o---o D
>   |\ /|
>   | X |
>   |/ \|
> E o---o F 
> 
> needs 5 colours.

  It does not need 5 colours, since E/F can have the same two colours as 
A/B.

Jim