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.

Improve this question
$\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$
    – Zsbán Ambrus
    Commented 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
    Commented 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$
    – Brendan McKay
    Commented 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
    Commented Aug 31, 2013 at 14:06

1 Answer 1

Reset to default
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$?

Improve this answer
$\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
    Commented 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
    Commented 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
    Commented Aug 30, 2013 at 23:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .