How to check that given graph is Bipartite or not?

Usage
1

How to check that given graph is Bipartite or not.,? Please provide me R syntax with Graph G=C5. It my kind request

3

Thanks. But when I make graph C5 using g=make_graph( ) & use is_bipartite(g) then its not working.

4

When I tried the same for cycle with 4 vertices C4, output is FALSE. But C4 is Bipartite graph. Please clear my doubt.

5

I’m sorry, you’re right. I deleted my post from above so it wouldn’t confuse future readers.

igraph uses the term “bipartite” somewhat idiosyncratically. It mostly applies to graph data structures that have a logical “type” vertex attribute, marking each vertex as belonging to one or the other partition. It does not matter if there are edges between two partitions. The function is_bipartite will only check if the graph has the type vertex attribute, and that’s it.

To decide whether a graph is bipartite, as a mathematician would mean it, you can use bipartite_mapping().

Example:

> c4 <- make_ring(4)
> bipartite_mapping(c4)
$res
[1] TRUE

$type
[1] FALSE  TRUE FALSE  TRUE

> c5 <- make_ring(5)
> bipartite_mapping(c5)
$res
[1] FALSE

$type
logical(0)

The $res component of the result tells you whether the graph is bipartite. The $type component gives you a specific partitioning, if this is possible.

6

Thanks a a lot. why $type FALSE TRUE FALSE TRUE is showing? What do you mean by this.? Please clear it sir.
################
KORE S.U
Head
Dept of Maths,
S.K.College,Jalkot
Maharashtra State,
INDIA

7

The nth truth value in the $types vector indicates which partition the nth vertex belongs to. FALSE = first partition, TRUE = second partition.

8

A post was split to a new topic: Plot Petersen graph