Macaulay2 » Documentation
Packages » EdgeIdeals :: isBipartite
next | previous | forward | backward | up | index | toc

isBipartite -- determines if a graph is bipartite

Synopsis

Description

The function isBipartite determines if a given graph is bipartite. A graph is said to be bipartite if the vertices can be partitioned into two sets W and Y such that every edge has one vertex in W and the other in Y. Since a graph is bipartite if and only if its chromatic number is 2, we can check if a graph is bipartite by computing its chromatic number.

i1 : S = QQ[a..e];
 
i2 : t = graph {a*b,b*c,c*d,a*e} -- a tree (and thus, bipartite)

o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o2 : Graph
 
i3 : c5 = cycle S -- 5-cycle (not bipartite)

o3 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {a, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o3 : Graph
 
i4 : isBipartite t

o4 = true
 
i5 : isBipartite c5

o5 = false

See also

Ways to use isBipartite:

For the programmer

The object isBipartite is a method function.