[Nauty-list] labelg with coloured graphs

Matthew Skala mskala at cs.umanitoba.ca
Sat May 5 04:13:18 EST 2012

On Fri, 4 May 2012, Sterten at aol.com wrote:
> add one vertex for each color and connect the n original vertices to their
> color-vertex
> connect the color vertices with each other
> one 5th additional vertex connects to the n original ones
> and to one 6th that has only that one edge
> 6 is unique with only 1 edge
> 5 is uniqe as neighbor of 6
> the colors are unique as non-neighbors of 6

Thanks for the suggestion.  I'd have to change it slightly because what
you describe makes the colours interchangeable, and mine are not - but
it's easy to imagine adding two or three more vertices in such a way as to
render the four "colour" vertices distinguishable from each other.

Thinking about it some more, I think I could give the added vertices known
indices and use labelg's -f option to add colouring to them, while keeping
all my original vertices in a single colour class:  four new vertices at
indices 0,1,2,3, each with its own unique colour specified by -f; all the
original vertices get the remaining indices, a fifth colour, and an edge
to the appropriate "colour" vertex.  That way all graphs with the same
number of vertices have the same -f string, which will allow labelg to
Matthew Skala
Postdoctoral Fellow, University of Manitoba
mskala at cs.umanitoba.ca

More information about the Nauty mailing list