[Nauty] Re: Generation of edge-colored graphs

Gunnar Brinkmann Gunnar.Brinkmann at UGent.be
Thu Oct 7 14:33:01 EST 2004

Dear Pavan,

You wrote

> Hello,
> I was wondering if one could use/modify 'geng' to generate all
> non-isomorphic edge-colored graphs on n vertices with k-colors. If not
> what would be the best way to generate them fast.
> Similarly for vertex-colored graphs.

It is a typical case where the homomorphism principle can be easily
applied. If you don't know what it is and can't find it in the literature,
I can send you a text to describe it. The result will be a VERY
fast program (at least if the number of colours are not too close to the
chromatical index/number), but of course some programming using geng
and nauty must be done.



Gunnar Brinkmann
Applied Mathematics and Computer Science
Ghent University
Krijgslaan 281 - S9
B - 9000 Ghent

email: Gunnar.Brinkmann at UGent.be

phone: +32-9-264.48.07, Fax: +32-9-264.49.95

More information about the Nauty mailing list