Determining Complete Multipartite Graphs (Specifically Tripartite)

savecancel

You're getting that error because there is no is_multipartite method on graphs in Sage, nor is there a multipartite_sets method. You can use the coloring method to get what you need since a tripartite graph is 3-colourable. Thus, you could do something like the following: (To simplify things, I'll just consider the m > 1 case.)

def is_complete_multipartite(m):
    assert m > 1
    def is_complete_m_partite(g):
        coloring = g.coloring()
        if coloring is None: #empty graph
            return False
        return len(coloring) == m and g.num_edges() == mul(map(len, coloring))
    return is_complete_m_partite

Then, you'd use it like

dd = filter(is_complete_multipartite(3), d)

to test for complete tripartiteness.