63.28 IsBipartite

IsBipartite( gamma )

This boolean function returns true if and only if the graph gamma, which must be simple, is bipartite, i.e. if the vertex set can be partitioned into two null graphs (which are called bicomponents or parts of gamma).

See also Bicomponents, EdgeGraph, and BipartiteDouble.

    gap> gamma := JohnsonGraph(4,2);
    rec(
      isGraph := true,
      order := 6,
      group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2 ],
      adjacencies := [ [ 2, 3, 4, 5 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
          [ 3, 4 ] ],
      isSimple := true )
    gap> IsBipartite(gamma);
    false
    gap> delta := BipartiteDouble(gamma);
    rec(
      isGraph := true,
      order := 12,
      group := Group( ( 1, 5)( 2, 6)( 7,11)( 8,12), ( 1, 3)( 4, 6)( 7, 9)
        (10,12), ( 2, 3)( 4, 5)( 8, 9)(10,11), ( 1, 7)( 2, 8)( 3, 9)
        ( 4,10)( 5,11)( 6,12) ),
      schreierVector := [ -1, 3, 2, 3, 1, 2, 4, 4, 4, 4, 4, 4 ],
      adjacencies := [ [ 8, 9, 10, 11 ] ],
      representatives := [ 1 ],
      isSimple := true,
      names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
          [ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
          [ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
          [ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
    gap> IsBipartite(delta);
    true 

Previous Up Top Next
Index