search

math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
15 stars 6 forks source link

Update invariant: bipartite number #402

Closed cjoshea9 closed 7 years ago

cjoshea9 commented 7 years ago 
def bn(g):
    """
    Defined as the largest number of vertices that induces a bipartite subgraph

    sage: bn(graphs.PetersenGraph())
    7
    sage: bn(c4)
    4
    sage: bn(graphs.CompleteGraph(3))
    2
    """
    return len(bs(g, [], g.vertices()))
rbarden commented 7 years ago

Just to be a bit quicker for the bipartite graphs, 

def bipartite_number(g):
    """
    Defined as the largest number of vertices that induces a bipartite subgraph

    sage: bn(graphs.PetersenGraph())
    7
    sage: bn(c4)
    4
    sage: bn(graphs.CompleteGraph(3))
    2
    """
    if g.is_bipartite():
        return g.order()
    return len(bs(g, [], g.vertices()))