# Generating k-partite graphs

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.

• Have you checked Donald Knuth's TAOCP volume 4 for references yet? I think it covers similar problems, such as generating all trees. – Zsbán Ambrus Aug 30 '13 at 9:38
• I have not. I'll have to get my hands on a copy of that book. Thank you for the suggestion! – caw Aug 30 '13 at 16:08
• 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. – Brendan McKay Aug 31 '13 at 0:52
• Ideally, I'd like graphs that are properly colored with t colors (i.e. $\chi(G) = t$). – 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 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$?
• 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$. – caw Aug 30 '13 at 15:16
• 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. – Jernej Aug 30 '13 at 18:38