[Nauty] Re: Generation of edge-colored graphs

[Gunnar Brinkmann]

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



---------------------------------------------------------

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