[Nauty-list] labelg with coloured graphs

Brendan McKay bdm at cs.anu.edu.au
Sat May 5 11:48:10 EST 2012

Although Gordon's suggestion of calling nauty yourself is the
best in the long term, your method suggested here is the best
for a quick solution.


* Matthew Skala <mskala at cs.umanitoba.ca> [120505 04:13]:
> 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
> work.
> -- 
> Matthew Skala
> Postdoctoral Fellow, University of Manitoba
> mskala at cs.umanitoba.ca
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list

More information about the Nauty mailing list