[Nauty] Handling vertex and edge coloured graph

Roger Ting rogermht at cs.mu.OZ.AU
Tue Aug 16 20:40:30 EST 2005

Hi All,
    There seems to be a confusion between vertex  and edge label  and 
vertex and edge colour. I wasn't aware of the
difference until lately. Graph theorist seems to differentiate between 
labelling and colouring. To correct my mistake, i
was talking about vertex and edge label. After some thought, i think  i 
can use the incidence edge label as a way to 
create vertex label. For example:

vertex 1 has label 1 and connected to edges with label  1 and 2
vertex 2 has label 1 and connected to edges with label 1 and 3

Therefore, these 2 vertices should be treated as having distinct label 
even though  the  vertex labelling is correct.
It seems to be a correct way but i am not sure how to prove that this  
correct formally.  It seems similar
to the way nauty divides the vertex set according to their degree.  Any 
feedback on this subject will be very


Roger Ting wrote:

> Hi all,
>    I know Nauty handle vertex coloured simple and undirected graph. 
> Can it handle vertex and edge coloured  graph?
> If not, how do you incorporate edge colour information into a vertex 
> coloured simple and undirected graph and let
> nauty handle it ?
> Cheers
> Roger
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list

More information about the Nauty mailing list