Distributed assignment of multiple colors to a vertex

Hi everyone...

I'm new to graph theory and have a question regarding carrying out
graph coloring in a distributed manner.

I'm listing my constraints:

1. adjacent vertices cannot have the same color (nothing new here!)
2. a vertex and all it's adjacent neighbours must include ALL the
colors in the graph, G.

Because of constraint no. 2, I'm thinking of assigning multiple colors
to a single vertex.

Just to illustrate my problem further, I'm giving an example. Let's say
I've 6 vertices and they're connected using the following connectivity
matrix:

V1 V2 V3 V4 V5 V6
V1 x 1 0 0 1 0
V2 1 x 1 0 0 1
V3 0 1 x 1 0 1
V4 0 0 1 x 0 1
V5 1 0 0 0 x 1
V6 0 1 1 1 1 x

Suppose they're assigned colors using a normal coloring algorithm, they
might have the following assignment:

V1: 1, V2: 2, V3: 3, V4: 2, V5: 2 and V6: 1.

The problem with such an assignment is that V5 and V1 for instance, are
not connected to any vertex that has color 3.

I'd like to know if there already are any algorithms out there that can
solve such a problem or do I need to devise a new solution? Also, I
couldn't really find any material which deals with assigning multiple
colors to a single vertex... has anyone ever had the need to do
something like this? :) Or is this something that should be avoided...
and if so why?

Thanks for your comments...
Stickman

.

Relevant Pages