Colouring Graphs

[Jim Nastos]

On Mon, 3 Feb 2003, Jon Perry wrote:

> OK, however using such an edge-colouring can increase the number of colours
> needed.

  Perhaps you still don't understand what I'm saying.
  This will be reflected in the graph G'. For example, with your graph 
given below, G' will have B adjacent to C because they are both in M(r) on 
v=A. And D will be adjacent to E as they are in M(w) for v=F. And C will 
be adjacent to F because of vertex E.
  Your graph becomes the graph I give below.

> A 1-r-2 B
>   |   |
>   r   b
>   |   |
> C 3-b-1 D
>   |   |
>   w   w
>   |   |
> E 2-w-4 F

A o---o B
  |  /|
  | / |
  |/  |
C o---o D
  |\ /|
  | X |
  |/ \|
E o---o F 

  And any valid colouring (yes, including the minimum ones) for this new 
graph G' will be valid for your graph with edge-colour constraints. For 
example, A=D=1, B=E=2, C=3, F=4 is minimum for G' and also for G, which is 
the colouring you gave. It in not hard to see that the chromatic number 
"increased" to 4 in constructing this G'.
  *ANY* valid colouring for G' will be valid for G, and minimality is 
conserved. Furthermore, for any normal graph, H, I can construct one of 
your coloured-edge-consrained graphs G such that G' formed from G is 
exactly H.

Jim