2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\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$ Aug 30, 2013 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, 2013 at 16:08
  • 2
    $\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$ Aug 31, 2013 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, 2013 at 14:06

1 Answer 1

3
$\begingroup$

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$?

$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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