is_bipartite() is confusing / problematic

[szhorvat]

Before you read further, please guess what you think the is_bipartite() function does, if you are not already familiar with it.

---

No, it's not the same as igraph_is_bipartite() in C, .is_bipartite() in Python or IGBipartiteQ[] in Mathematica. Those functions decide if the graph is bipartite (i.e. 2-colourable) in the graph theoretical sense.

is_bipartite() in R simply checks whether a graph has a type vertex attribute. This is documented, but in a way that is somewhat confusing, and easy to miss. It's at the bottom of the doc page:

is_bipartite() checks whether the graph is bipartite or not. It just checks whether the graph has a vertex attribute called type.

In plain words, the term "bipartite" in R/igraph is used differently than just about anywhere else. We should consider changing this terminology in igraph 2.0, so it lines up better with common usage.

2-colourability is checked by bipartite_mapping().

[ghost]

The problem being discussed is regarding the is_bipartite() function in the R/igraph package. As opposed to its name, the function doesn't determine whether a graph is 2-colorable or bipartite. Instead, it only checks whether the graph has a vertex attribute called "type".

To address this issue, it has been recommended to change the terminology used in R/igraph to better align with common usage. It has also been suggested that the bipartite_mapping() function be used instead to determine if a graph is 2-colorable or bipartite in the graph theoretical sense.

I hope this explanation helps clarify the issue at hand.