Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond bipartite graph generation is supported. Any help, whether it's a pointer to a paper(s) or source code, would be immensely useful in my research.

EDIT: One variation of my problem requires that all graphs are also regular, so I can assume a fixed degree for every node. I'm still not sure if that helps.

  • $\begingroup$ Have you checked Donald Knuth's TAOCP volume 4 for references yet? I think it covers similar problems, such as generating all trees. $\endgroup$ – Zsbán Ambrus Aug 30 '13 at 9:38
  • $\begingroup$ I have not. I'll have to get my hands on a copy of that book. Thank you for the suggestion! $\endgroup$ – caw Aug 30 '13 at 16:08
  • 1
    $\begingroup$ Do you want graphs that can be properly coloured with $t$ colours, or graphs that are properly coloured with $t$ colours? The generation problem is entirely different for these two options. $\endgroup$ – Brendan McKay Aug 31 '13 at 0:52
  • $\begingroup$ Ideally, I'd like graphs that are properly colored with t colors (i.e. $\chi(G) = t$). $\endgroup$ – caw Aug 31 '13 at 14:06

For bipartite graphs you can use McKay's genbg program that is shipped with the nauty package. For small values of $n$ (up to 11) you can use Sage in the following way:

sage: for G in graphs.nauty_geng("n"):
....:     if G.chromatic_number() == k:
....:         # do something with it

If you need something more efficient then you'll have to be more specific. Do you impose any other structure on your graphs? What values of $n$ are you interested in? What values of $k$?

  • $\begingroup$ As I mention in the edit above, I can impose the constraint that the graph is regular. I am interested in as many values of $n$ and $k$ as possible, so long as $k \geq 3$. $\endgroup$ – caw Aug 30 '13 at 15:16
  • $\begingroup$ You can do that quite quickly (less than a day) for $n$ up to $10-11$ For $12$ its also quite feasible but for $n > 13$ I don't think there is a way to do this without some additional constraints. $\endgroup$ – Jernej Aug 30 '13 at 18:38
  • $\begingroup$ Unfortunately, the only other constraint I can impose is that of degree regularity. It looks like I'm a bit stuck here. :-\ $\endgroup$ – caw Aug 30 '13 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.