# Determining Complete Multipartite Graphs (Specifically Tripartite)

I have been reading the Sage References, and it does not seem that complete multipartite graphs are defined in Sage yet. I have tried to critique the following two lines of code to see if it would work for complete multipartite graphs.

def is_complete_multipartite(p):
return p.is_multipartite() and p.num_edges() == mul(map(len, g.multipartite_sets()))

dd = filter(is_complete_multipartite, d)


I get a "graph attribute needed" error. I just wanted to verify that this is the case. Thanks again for the help!

edit retag close merge delete

Sort by ยป oldest newest most voted

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.

more

Thanks! I'll give it try.

( 2011-09-15 16:28:43 +0200 )edit