This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
please add a link to petri-net, as an application of bi-partite graphs. thank you! andrew frank — Preceding unsigned comment added by 82.218.14.12 (talk • contribs) 18:05, 16 February 2006
I think the heading "For the ubiquitous computing formalism, see bigraph" should be removed. One reason is that the link to 'bigraph' mis-represents what a bi-partite graph is! The second reason is that 'ubiquitous computing' seems a very wooly area whereas Graph Theory aims to be a precise part of mathematics. To suggest that graph theory is somehow within 'ubiquitous computing' is therefore inappropriate. John Carter 89.204.177.130 (talk) 04:02, 29 August 2011 (UTC)[reply]
That heading is just a kindness to people looking for the computing concept who came here by accident. It doesn't imply there is any actual connection. McKay (talk) 04:34, 29 August 2011 (UTC)[reply]
It is necessary to link from "Bigraph" to "Bipartite graph" because a bipartite graph is sometimes called a bigraph, and hence confusion could result. But the reverse is not so: nobody would ever refer to a bigraph as a bipartite graph. There is no confusion, so I believe the disambiguating heading should be removed from this page. Wicko3 (talk) 09:50, 27 November 2011 (UTC)[reply]
I agree with McKay that the heading is useful and should stay. Also, a bipartite graph is a subset of the class of connected graphs and that fact should appear in its definition. I added that stipulation, but no entry exists for "connected graph". jaydee000
This article contains almost all necessary information and enough references to be a good article, however the article is somewhat messy, and there is no good flow in it. Should someone feel the need to improve this article, it should be done by rewriting it for better readability while preserving the information there. Any other suggestions to what should be done? --80.202.100.133 (talk) 15:19, 27 February 2012 (UTC)[reply]
I think a lot of the flow problems had to do with bad section ordering. I've reordered the sections and am now working on improving the writing and sourcing within the sections. —David Eppstein (talk) 22:02, 27 August 2012 (UTC)[reply]
In case it helps, below is a drawing showing how to partition a connected graph G with only even length cycles into two sets of vertices U and V. The method is to use the spanning tree (in red), and to alternate two colors (blue and white) starting at a root r of the spanning tree.
"The spectrum of a graph is symmetric if and only if it's a bipartite graph."
The reference article rather says "if a graph is bipartite, then its spectrum is symmetric".
A triangle (i.e. complete graph on 3 vertices) has symmetric spectrum (as does any undirected graph as mentioned elsewhere on the wikipage) but it is not a bipartite graph, since it has an odd cycle. Thus, the converse is not true.
The first use I've seen of the term "partite sets" is in this article. Historically, the sets U and V are called the "parts" of the graph. To check this, I googled "partite sets" and found about 12,000 references whereas the much longer term "parts of a bipartite graph" has about 93,000 references. Thus, I have edited the article to use the term "parts". — Preceding unsigned comment added by Hpfister (talk • contribs) 15:41, 23 March 2016 (UTC)[reply]
Please add a clarification (I don't feel up to that myself) that when testing for bipartite graphs using depth-first or breadth-first search one has to take into account the possibility of disconnected graphs. In that case such an algorithm will only check the connected component that is reachable from the starting vertex. So in order to correctly determine if a given graph is bipartite one has to make sure that all vertices are actually visited, for example by maintaining a count of visited vertices or by actually removing edges from the datastructure and reiterate while there are edges left. — Preceding unsigned comment added by 82.83.186.53 (talk) 06:06, 1 August 2017 (UTC)[reply]
I changed "depth first search tree" to "depth first search forest" etc in that section. I don't think anything more than that needs to be done to handle disconnected graphs. —David Eppstein (talk) 07:08, 1 August 2017 (UTC)[reply]
Here we say that a graph is bipartite if and only if its vertices can be partitioned into sets A and B such that the sum of the degrees of vertices in each partition is equal, and any vertex’s degree is less than or equal to the cardinality of the other set. I don’t see why this converse is true. Two disconnected K3 graphs seem to be a counterexample. Also, there isn’t a source to this, and I’m wondering where it came from. — Preceding unsigned comment added by Bbk001 (talk • contribs) 02:18, 1 January 2022 (UTC)[reply]
Oh, I see. That looks likely to be incorrect to me, and it's definitely unsourced. I'll remove it, and the non-characterization (upper bound on #edges) in the next bullet. —David Eppstein (talk) 16:45, 1 January 2022 (UTC)[reply]
Consider a simple graph with the only vertix (obviously, it is empty). It has no an odd cycle (no cycles at all), but it is not bipartite, because one vertix cannot be diuvided onto two disjoined nonempty parts. Spectorsky (talk) 16:21, 25 November 2023 (UTC)[reply]